【线段树(sum,add)】P1083 借教室

分享图片
  1 #include<iostream>
  2 #include<string>
  3 #include<queue>
  4 #include<stack>
  5 #include<vector>
  6 #include<map>
  7 #include<cstdio>
  8 #include<cstdlib>
  9 #include<algorithm>
 10 #include<set>
 11 #include<list>
 12 #include<iomanip>
 13 #include<cstring>
 14 #include<cmath>
 15 #include<limits>
 16 using namespace std;
 17 
 18 #define au auto
 19 #define debug(i) cout<<"<debug> "<<i<<"<\debug>"<<endl
 20 #define mfor(i,a,b) for(register int i=(a);i<=(b);i++)
 21 #define mrep(i,a,b) for(register int i=(a);i>=(b);i--)
 22 #define LLL __int128
 23 #define Re register
 24 #define il inline
 25 #define mem(a,b) memset(a,(b),sizeof(a))
 26 typedef pair<int, int> intpair;
 27 typedef long long int LL;
 28 const int INF = 0x3f3f3f3f;
 29 const long long int INFLL = 0x3f3f3f3f3f3f3f3f;
 30 
 31 const int maxn = 5000010;
 32 int a[maxn];
 33 int n, m;
 34 
 35 #define lc(x) x<<1
 36 #define rc(x) x<<1|1
 37 
 38 il int min(int a, int b)
 39 {
 40     return a > b ? b : a;
 41 }
 42 
 43 struct tree
 44 {
 45     int a;
 46     int l, r;
 47     int tag;
 48     tree()
 49     {
 50         tag = 0;
 51         l = 0;
 52         r = 0;
 53         a = 0;
 54     }
 55 }node[maxn];
 56 
 57 void build(int x, int l, int r)
 58 {
 59     node[x].l = l;
 60     node[x].r = r;
 61     if (l == r)
 62     {
 63         node[x].a = a[l];
 64         return;
 65     }
 66     int mid = (l + r) >> 1;
 67     build(lc(x), l, mid);
 68     build(rc(x), mid + 1, r);
 69     node[x].a = min(node[lc(x)].a, node[rc(x)].a);
 70 }
 71 
 72 inline void push_down(int x)
 73 {
 74     node[lc(x)].tag += node[x].tag;
 75     node[lc(x)].a += node[x].tag;
 76     node[rc(x)].a += node[x].tag;
 77     node[rc(x)].tag += node[x].tag;
 78     node[x].tag = 0;
 79 }
 80 
 81 inline void update(int left, int right, int x, int k)
 82 {
 83     if (left <= node[x].l && node[x].r <= right)
 84     {
 85         node[x].a += k;
 86         node[x].tag += k;
 87         return;
 88     }
 89     push_down(x);
 90     int mid = (node[x].l + node[x].r) >> 1;
 91     if (left <= mid) update(left, right, lc(x), k);
 92     if (right > mid) update(left, right, rc(x), k);
 93     node[x].a = min(node[lc(x)].a, node[rc(x)].a);
 94 }
 95 
 96 int query(int left, int right, int x)
 97 {
 98     int res = INF;
 99     if (left <= node[x].l && node[x].r <= right) return node[x].a;
100     int mid = (node[x].l + node[x].r) >> 1;
101     if (left <= mid) res = min(res, query(left, right, lc(x)));
102     if (right > mid) res = min(res, query(left, right, rc(x)));
103     return res;
104 }
105 
106 int main()
107 {
108     ios::sync_with_stdio(0);
109     cin.tie(0);
110     cin >> n >> m;
111     mfor(i, 1, n)
112     {
113         cin >> a[i];
114     }
115     build(1, 1, n);
116     mfor(i, 1, m)
117     {
118         int a, b, c;
119         cin >> a >> b >> c;
120         update(b, c, 1, -a);
121         if (query(1, n, 1) < 0)
122         {
123             cout << -1 << endl;
124             cout << i;
125             return 0;
126         }
127     }
128     cout << 0;
129 }
View Code
相关文章
相关标签/搜索