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];
  5. void UPDATE(int id, int l, int r, int i, int v)
  6. {
  7.     if (l>i || r<i) return;
  8.     else if (l==r)
  9.     {
  10.         st[id]=v;
  11.         return;
  12.     }
  13.     int mid=(l+r)/2;
  14.     if (i<=mid) UPDATE(id*2,l,mid,i,v);
  15.     else UPDATE(id*2+1,mid+1,r,i,v);
  16.     st[id]=min(st[id*2],st[id*2+1]);
  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.     res=GETL(id*2,l,mid,u,v,k);
  24.     if (res!=-1) return res;
  25.     else 
  26.     {
  27.         res=GETL(id*2+1,mid+1,r,u,v,k);
  28.         if (res!=-1) return res;
  29.     }
  30.     return -1;
  31. }
  32. int GETR(int id, int l, int r, int u, int v, int k)
  33. {
  34.     int res=-1,mid=(l+r)/2;
  35.     if ((st[id]>k) || (l>v || r<u)) return -1;
  36.     if (l==r) return r;
  37.     res=GETR(id*2+1,mid+1,r,u,v,k);
  38.     if (res!=-1) return res;
  39.     else 
  40.     {
  41.         res=GETR(id*2,l,mid,u,v,k);
  42.         if (res!=-1) return res;
  43.     }
  44.     return -1;
  45. }
  46. signed main()
  47. {
  48.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  49.     cin>>n>>q;
  50.     for (int i=1;i<=n;i++) cin>>a[i];
  51.     for (int i=1;i<=n;i++) UPDATE(1,1,n,i,a[i]);
  52.     for (int i=1;i<=q;i++)
  53.     {
  54.         int t;
  55.         cin>>t;
  56.         if (t==1)
  57.         {
  58.             int pos,k;
  59.             cin>>pos>>k;
  60.             UPDATE(1,1,n,pos,k);
  61.         }
  62.         else
  63.         {
  64.             int l,r,k;
  65.             cin>>l>>r>>k;
  66.             cout<<GETL(1,1,n,l,r,k)<<' '<<GETR(1,1,n,l,r,k)<<'\n';
  67.         }
  68.     }
  69.     return 0;
  70. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lC82O7
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!