fork download 
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int N = 1<<17;
  9. const int Q = 1<<14;
  10. const int MAX = 1<<10;
  11.  
  12. int n,q,sq;
  13. int a[N];
  14. int cnt[MAX];
  15. int ans[Q];
  16.  
  17. struct query {
  18.     int l, r, num;
  19.  
  20.     bool operator <(const query &k) const {
  21.         int block1, block2;
  22.         block1 = l/sq;
  23.         block2 = k.l/sq;
  24.         if(block1<block2) return true;
  25.         if(block1>block2) return false;
  26.         return r<k.r;
  27.     }
  28. }b[Q];
  29.  
  30. void input() {
  31.     int i;
  32.     memset(cnt,0,sizeof(cnt));
  33.     scanf("%d %d", &n, &q);
  34.     sq=sqrt(n);
  35.     for(i=1;i<=n;i++) {
  36.         scanf("%d", &a[i]);
  37.     }
  38.     for(i=1;i<=q;i++) {
  39.         scanf("%d %d", &b[i].l, &b[i].r);
  40.         b[i].num=i;
  41.         b[i].l++;
  42.         b[i].r++;
  43.     }
  44.     sort(b+1,b+1+q);
  45. }
  46.  
  47. void solve() {
  48.     int l,r,i,j,last;
  49.     l=1;
  50.     r=1;
  51.     cnt[a[1]]++;
  52.  
  53.     for(i=1;i<=q;i++) {
  54.         while(l>b[i].l) {
  55.             l--;
  56.             cnt[a[l]]++;
  57.         }
  58.  
  59.         while(r>b[i].r) {
  60.             cnt[a[r]]--;
  61.             r--;
  62.         }
  63.  
  64.         while(r<b[i].r) {
  65.             r++;
  66.             cnt[a[r]]++;
  67.         }
  68.  
  69.         while(l<b[i].l) {
  70.             cnt[a[l]]--;
  71.             l++;
  72.         }
  73.  
  74.         ans[b[i].num]=1000000;
  75.         last=-1;
  76.  
  77.         for(j=1;j<=1000;j++) {
  78.             if(cnt[j]>1) {
  79.                 ans[b[i].num]=0;
  80.                 break;
  81.             }
  82.  
  83.             if(cnt[j]) {
  84.                 if(last==-1) last=j;
  85.                 else {
  86.                     ans[b[i].num]=min(ans[b[i].num],j-last);
  87.                     last=j;
  88.                 }
  89.             }
  90.         }
  91.     }
  92.  
  93.     for(i=1;i<=q;i++) printf("%d\n", ans[i]);
  94. }
  95.  
  96. int main() {
  97.     int i,tests;
  98.  
  99.     scanf("%d", &tests);
  100.  
  101.     for(i=1;i<=tests;i++) {
  102.         input();
  103.         printf("Case %d:\n", i);
  104.         solve();
  105.     }
  106.  
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0s 3872KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/LUOIHR
language:
C++14 (gcc 8.3)
created:
9 years 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!