fork download
copy 
  1. #include <bits/stdc++.h>
  2. // #define 
  3. using namespace std;
  4. int a[1000007],n,q,ans[1000007];
  5. int nxt[1000007],f[1000007];
  6. pair<int,int> vt[1000007];
  7. int st[4000007];
  8. vector<pair<pair<int,int>,pair<int,int>> > tv[1000007]; 
  9. int tim(int x) {
  10.     int l=1,r=n,ans=1;
  11.     while (l<=r) {
  12.         int g=(l+r)>>1;
  13.         if (vt[g].first<=x) {
  14.             ans=g;
  15.             l=g+1;
  16.         } else r=g-1;
  17.     }
  18.     return ans;
  19. }
  20. void up(int id,int l,int r,int i,int x) {
  21.     if (l>i||r<i) return ;
  22.     if (l>=i&&r<=i) {
  23.         st[id]=max(st[id],x);
  24.         return ;
  25.     }
  26.     int g=(l+r)>>1;
  27.     up(id<<1,l,g,i,x);
  28.     up(id<<1|1,g+1,r,i,x);
  29.     st[id]=max(st[id<<1],st[id<<1|1]);
  30. }
  31. int wlak(int id, int l,int r,int u,int v,int x) {
  32.     if (l>v||r<u) return -1;
  33.     if (l==r) {
  34.         if (st[id]>=x) return vt[l].first; else return -1;
  35.     }
  36.     int g=(l+r)>>1,ans=-1;
  37.     if (st[id<<1]>=x) ans=wlak(id<<1,l,g,u,v,x);
  38.     if (ans==-1) {
  39.         ans=wlak(id<<1|1,g+1,r,u,v,x);
  40.     }
  41.     return ans;
  42. }
  43. int tim1(int x) {
  44.     int l=1,r=n,ans=0;
  45.     while (l<=r) {
  46.         int g=(l+r)>>1;
  47.         if (vt[g].first>=x) {
  48.             ans=g;
  49.             r=g-1;
  50.         } else l=g+1;
  51.     }
  52.     return ans;
  53. }
  54. int get(int id,int l,int r,int u,int v) {
  55.     if (l>v||r<u) return 0;
  56.     if (l>=u&&r<=v) return st[id];
  57.     int g=(l+r)>>1;
  58.     return max(get(id<<1,l,g,u,v),get(id<<1|1,g+1,r,u,v));
  59. }
  60. int32_t main() 
  61. {
  62.     ios_base::sync_with_stdio(0);
  63.     cin.tie(0);
  64.     cin>>n>>q;
  65.     for (int i=1;i<=n;i++) {
  66.         cin>>a[i];
  67.         vt[i]={a[i],i};
  68.     }
  69.     for (int i=1;i<=4*n;i++) st[i]=0;
  70.     sort(vt+1,vt+n+1);
  71.     vt[0].first=-1;
  72.     vt[n+1].first=-1;
  73.     int d=0;
  74.     for (int i=n;i>0;i--) {
  75.         if (vt[i].first==vt[i+1].first) {
  76.             nxt[vt[i].second]=d;
  77.         } else {
  78.             nxt[vt[i].second]=0;
  79.             d=vt[i].second;
  80.         }
  81.         // nxt[vt[i].second]=d;
  82.     }   
  83.  
  84.     nxt[n+1]=n+1;
  85.     for (int i=1;i<=q;i++) {
  86.         int l,r,u,v;
  87.         cin>>l>>r>>u>>v;
  88.         tv[l].push_back({{i,r},{u,v}});
  89.     }
  90.     // for (int i=1;i<=n;i++) cout<<vt[i].first<<' ';
  91.     // cout<<'\n';
  92.     for (int i=1;i<=n;i++) {
  93.  
  94.         up(1,1,n,tim(a[i]),nxt[i]);
  95.         for (pair<pair<int,int>,pair<int,int>> ii:tv[i]) {
  96.             int u=tim1(ii.second.first),v=tim(ii.second.second);
  97.             if (u==0||v==0) {
  98.                 ans[ii.first.first]=-1;
  99.                 continue ;
  100.             }
  101.             // cout<<st[1]<<'\n';
  102.             // cout<<ii.second.first<<' '<<ii.second.second<<' '<<u<<' '<<v<<'\n';
  103.             ans[ii.first.first]=wlak(1,1,n,u,v,ii.first.second);
  104.         }
  105.         // for (int i=1;i<=n;i++) cout<<get(1,1,n,i,i)<<' ';
  106.         // cout<<'\n';
  107.     }   
  108.     for (int i=1;i<=q;i++) cout<<ans[i]<<'\n';
  109.     return 0;
  110. }
Success #stdin #stdout 0.01s 27068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ioMgyI
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!