fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,m,a[400005],an[400005],ps[400005],st[1600006];
  5. map <int,int> mp;
  6. vector <pair<pair<int,int>,pair<int,int>>> ve[400005];
  7. void UPDATE(int id, int l, int r, int i, int v)
  8. {
  9.     if (l>i || r<i) return;
  10.     else if (l==r) 
  11.     {
  12.         st[id]=v;
  13.         return;
  14.     }
  15.     int mid=(l+r)/2;
  16.     if (i<=mid) UPDATE(id*2,l,mid,i,v);
  17.     else UPDATE(id*2+1,mid+1,r,i,v);
  18.     st[id]=min(st[id*2],st[id*2+1]);
  19. }
  20. int GET(int id, int l, int r, int u, int v, int lim)
  21. {
  22.     if (l>v || r<u || st[id]>=lim) return 1e18;
  23.     else if (l==r) return l;
  24.     int mid=(l+r)/2;
  25.     int res=GET(id*2,l,mid,u,v,lim);
  26.     if (res!=1e18) return res;
  27.     else return GET(id*2+1,mid+1,r,u,v,lim);
  28. }
  29. signed main()
  30. {
  31.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  32.     cin>>n>>m;
  33.     for (int i=1;i<=n;i++) cin>>a[i];
  34.     for (int i=1;i<=m;i++) 
  35.     {
  36.         int l,r,c,d;
  37.         cin>>c>>d>>l>>r;
  38.         ve[r].push_back({{l,i},{c,d}});
  39.     }
  40.     for (int i=1;i<=n;i++)
  41.     {
  42.         UPDATE(1,1,n,a[i],i),ps[a[i]]=i;
  43.         for (pair <pair<int,int>,pair<int,int>> p : ve[i])
  44.         {
  45.             int l=p.first.first,idx=p.first.second,c=p.second.first,d=p.second.second;
  46.             an[idx]=GET(1,1,n,c,d,l);
  47.         }
  48.     }
  49.     for (int i=1;i<=m;i++)
  50.     {
  51.         if (an[i]==1e18) cout<<"OK \n";
  52.         else cout<<an[i]<<'\n';
  53.     }
  54.     return 0;
  55. }
Success #stdin #stdout 0.01s 13096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Hw7HIb
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!