P1083-借教室

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define _for(i,a,b) for(int i = (a);i < b;i ++)
  4 #define _rep(i,a,b) for(int i = (a);i > b;i --)
  5 #define INF 0x3f3f3f3f
  6 #define pb push_back
  7 #define maxn 1000039
  8 typedef long long ll;
  9 inline ll read()
 10 {
 11     ll ans = 0;
 12     char ch = getchar(), last = ' ';
 13     while(!isdigit(ch)) last = ch, ch = getchar();
 14     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
 15     if(last == '-') ans = -ans;
 16     return ans;
 17 }
 18 inline void write(ll x)
 19 {
 20     if(x < 0) x = -x, putchar('-');
 21     if(x >= 10) write(x / 10);
 22     putchar(x % 10 + '0');
 23 }
 24 struct need
 25 {
 26     int num;
 27     int st;
 28     int ed;
 29 };
 30 int n,m;
 31 need List[maxn];
 32 struct segtree
 33 {
 34     int l,r;
 35     ll add;
 36     ll Min;
 37     #define l(x) t[x].l
 38     #define r(x) t[x].r
 39     #define Min(x) t[x].Min
 40     #define add(x) t[x].add
 41  //   #define sum(x) t[x].sum
 42 }t[maxn<<2];
 43 int a[maxn];
 44 int N,M;
 45 
 46 void build(int p,int l,int r)
 47 {
 48     l(p) = l,r(p) = r;
 49     if(l==r){Min(p)=a[l];return ;}
 50     int mid = (l+r)/2;
 51     build(p*2,l,mid);
 52     build(p*2+1,mid+1,r);
 53   //  sum(p) = sum(p*2)+sum(p*2+1);
 54     Min(p) = min(Min(p*2),Min(p*2+1));
 55 }
 56 void spread(int p)
 57 {
 58     if(add(p))
 59     {
 60     //    sum(p*2) += add(p)*(r(p*2)-l(p*2)+1);
 61     //    sum(p*2+1) += add(p)*(r(p*2+1)-l(p*2+1)+1);
 62         Min(p*2) = add(p)+Min(p*2);
 63         Min(p*2+1) = add(p)+Min(p*2+1);
 64         add(p*2) += add(p);
 65         add(p*2+1) += add(p);
 66         add(p) = 0; 
 67     }
 68 }
 69 void change(int p,int l,int r,int d)
 70 {
 71   //  cout << l(p) << " " << r(p) << endl;
 72     if(l <= l(p) and r >= r(p))
 73     {
 74         Min(p) += d;
 75         add(p) += d;
 76         return ;
 77     }
 78     spread(p);
 79     int mid = (l(p)+r(p))/2;
 80     if(l <= mid)
 81         change(p*2,l,r,d);
 82     if(r > mid)
 83         change(p*2+1,l,r,d);
 84     Min(p) = min(Min(p*2),Min(p*2+1));
 85     
 86  //   cout << Min(p) << endl;
 87 }
 88 ll ask(int p,int l,int r)
 89 {
 90     if(l <= l(p) and r >= r(p))
 91         return Min(p);
 92     spread(p);
 93     int mid = (l(p)+r(p))/2;
 94     ll val = INT_MAX;
 95     if(l <= mid)
 96         val = min(val,ask(p*2,l,r));
 97     if(r > mid)
 98         val = min(val,ask(p*2+1,l,r));
 99     return val; 
100 }
101 int main()
102 {
103     n = read();m = read();
104     _for(i,1,n+1)
105         a[i] = read();
106     build(1,1,n);
107 
108     _for(i,1,m+1)
109     {
110         int num,st,ed;
111         num = read();
112         st = read();
113         ed = read();
114         change(1,st,ed,-num);
115         if(ask(1,st,ed)<0)
116         {
117             printf("-1
%d
",i);
118             return 0;
119         }
120     }
121     printf("0
");
122     return 0;
123 }
需要氧气