fork download 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("avx,avx2,fma,sse2")
  3. #pragma GCC optimization ("unroll-loops")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. #define int unsigned int
  7. #define fi first
  8. #define se second
  9. #define siz(x) (int)(x.size())
  10. const int maxN=5e5+5, can=sqrt(5e5+5)+1;
  11. struct ez{int l,r,id;};
  12.  
  13. int n, m, a[maxN], block[maxN], res[maxN], cnt[maxN];
  14. ez q[maxN];
  15.  
  16. // block[i] la so cac so xuat hien 1 lan duy nhat trong block;
  17. bool cmp(ez a1, ez a2)
  18. {
  19.     if((a1.l-1)/can==(a2.l-1)/can) return a1.r<a2.r;
  20.     else return a1.l<a2.l;
  21. }
  22.  
  23. void add(int pos)
  24. {
  25.     if(cnt[a[pos]]==1) block[(a[pos]-1)/can]--;
  26.     cnt[a[pos]]++;
  27.     if(cnt[a[pos]]==1) block[(a[pos]-1)/can]++;
  28. }
  29.  
  30. void vut(int pos)
  31. {
  32.     if(cnt[a[pos]]==1) block[(a[pos]-1)/can]--;
  33.     cnt[a[pos]]--;
  34.     if(cnt[a[pos]]==1) block[(a[pos]-1)/can]++;
  35. }
  36.  
  37. void solve()
  38. {
  39.     sort(q+1,q+m+1,cmp);
  40.     int cur_l=1, cur_r=0;
  41.     for(int i=1; i<=m; i+=1)
  42.     {
  43.         while(cur_r<q[i].r)
  44.         {
  45.             cur_r++;
  46.             add(cur_r);
  47.         }
  48.         while(cur_r>q[i].r)
  49.         {
  50.             vut(cur_r);
  51.             cur_r--;
  52.         }
  53.         while(cur_l<q[i].l)
  54.         {
  55.             vut(cur_l);
  56.             cur_l++;
  57.         }
  58.         while(cur_l>q[i].l)
  59.         {
  60.             cur_l--;
  61.             add(cur_l);
  62.         }
  63.         for(int j=0; j<=can; j+=1)
  64.         {
  65.             if(block[j])
  66.             {
  67.                 for(int k=j*can+1; k<=(j+1)*can; k+=1)
  68.                 {
  69.                     if(cnt[k]==1)
  70.                     {
  71.                         res[q[i].id]=k; break;
  72.                     }
  73.                 }
  74.                 break;
  75.             }
  76.         }
  77.     }
  78.     for(int i=1; i<=m; i+=1) cout<<res[i]<<'\n';
  79. }
  80.  
  81. int32_t main()
  82. {
  83.     ios_base::sync_with_stdio(0); cin.tie(0);
  84.     cin>>n;
  85.     for(int i=1; i<=n; i+=1) cin>>a[i];
  86.     cin>>m;
  87.     for(int i=1; i<=m; i+=1) cin>>q[i].l>>q[i].r, q[i].id=i;
  88.     solve();
  89. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/uFLW8y
language:
C++14 (gcc 8.3)
created:
10 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!