P1083-借教室

旧城等待， 2023-06-01 08:57 25阅读 0赞

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\n%d\n",i);
    118             return 0;
    119         }
    120     }
    121     printf("0\n");
    122     return 0;
    123 }

需要氧气

转载于:https://www.cnblogs.com/Asurudo/p/11613490.html