fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,q,j,a[600005],st[2400006],ans[6000005];
  4. pair <pair<int,int>,int> p[600005];
  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 GET(int id, int l, int r, int k)
  19. {
  20.     if (l==r) return l;
  21.     int mid=(l+r)/2;
  22.     if (st[id*2]<k) return GET(id*2,l,mid,k);
  23.     else return GET(id*2+1,mid+1,r,k);
  24. }
  25. signed main()
  26. {
  27.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  28.     cin>>n>>q;
  29.     for (int i=1;i<=n;i++) cin>>a[i];
  30.     for (int i=1;i<=n+1;i++) UPDATE(1,1,n+1,i,-1);
  31.     for (int i=1;i<=q;i++) cin>>p[i].first.second>>p[i].first.first,p[i].second=i;
  32.     j=1,sort(p+1,p+q+1);
  33.     for (int i=1;i<=n;i++)
  34.     {
  35.         UPDATE(1,1,n+1,a[i],i);
  36.         while (p[j].first.first==i) ans[p[j].second]=GET(1,1,n+1,p[j].first.second),j++;
  37.     }
  38.     for (int i=1;i<=q;i++) cout<<ans[i]<<'\n';
  39.     return 0;
  40. }
Success #stdin #stdout 0.01s 5724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RlJ2vo
language:
C++14 (gcc 8.3)
created:
1 day 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!