fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,q,a[300005],st[1200006],lz[1200006];
  5. void UPDATE(int id, int l, int r, int u, int v, int x)
  6. {
  7.     if (l>v || r<u) return;
  8.     else if (l>=u && r<=v)
  9.     {
  10.         st[id]+=x,lz[id]+=x;
  11.         return;
  12.     }
  13.     int mid=(l+r)/2;
  14.     st[id*2]+=lz[id],lz[id*2]+=lz[id],st[id*2+1]+=lz[id],lz[id*2+1]+=lz[id];
  15.     UPDATE(id*2,l,mid,u,v,x),UPDATE(id*2+1,mid+1,r,u,v,x);
  16.     st[id]=min(st[id*2],st[id*2+1]),lz[id]=0;
  17. }
  18. int GETL(int id, int l, int r, int u, int v, int k)
  19. {
  20.     int res=-1,mid=(l+r)/2;
  21.     if ((st[id]>k) || (l>v || r<u)) return -1;
  22.     if (l==r) return r;
  23.     st[id*2]+=lz[id],lz[id*2]+=lz[id],st[id*2+1]+=lz[id],lz[id*2+1]+=lz[id],lz[id]=0;
  24.     res=GETL(id*2,l,mid,u,v,k);
  25.     if (res!=-1) return res;
  26.     else 
  27.     {
  28.         res=GETL(id*2+1,mid+1,r,u,v,k);
  29.         if (res!=-1) return res;
  30.     }
  31.     return -1;
  32. }
  33. int GETR(int id, int l, int r, int u, int v, int k)
  34. {
  35.     int res=-1,mid=(l+r)/2;
  36.     if ((st[id]>k) || (l>v || r<u)) return -1;
  37.     if (l==r) return r;
  38.     st[id*2]+=lz[id],lz[id*2]+=lz[id],st[id*2+1]+=lz[id],lz[id*2+1]+=lz[id],lz[id]=0;
  39.     res=GETR(id*2+1,mid+1,r,u,v,k);
  40.     if (res!=-1) return res;
  41.     else 
  42.     {
  43.         res=GETR(id*2,l,mid,u,v,k);
  44.         if (res!=-1) return res;
  45.     }
  46.     return -1;
  47. }
  48. signed main()
  49. {
  50.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  51.     cin>>n>>q;
  52.     for (int i=1;i<=n;i++) cin>>a[i];
  53.     for (int i=1;i<=n;i++) UPDATE(1,1,n,i,i,a[i]);
  54.     for (int i=1;i<=q;i++)
  55.     {
  56.         int t,l,r,x;
  57.         cin>>t>>l>>r>>x;
  58.         if (t==1) UPDATE(1,1,n,l,r,x);
  59.         else cout<<GETL(1,1,n,l,r,x)<<' '<<GETR(1,1,n,l,r,x)<<'\n';
  60.     }
  61.     return 0;
  62. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qtx2IB
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!