fork(3) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <cmath>
  6. using namespace std;
  7. typedef long long int LL;
  8.  
  9. struct node{
  10.   int l;
  11.   int r;
  12.   int id;
  13. }u[311111];
  14.  
  15. int z;
  16. bool cool(node a,node b)
  17. {
  18.      if(a.l/z<b.l/z)
  19.         return true;
  20.      if(a.l/z>b.l/z)
  21.         return false;
  22.      return a.r<b.r;
  23. }
  24.  int cnt[1111111];
  25.  int ans[311111];
  26.  int v[311111];
  27.  
  28. int main()
  29. {
  30.  
  31.      //ios_base:: sync_with_stdio(false); cin.tie(0);
  32.  
  33.  
  34.     // freopen("input.in","r",stdin);
  35.  
  36.         int n;cin>>n;
  37.         int fuk=0;
  38.         z=sqrt(n);
  39.       //  vector<int>v(n);
  40.  
  41.         for(int i=0;i<n;i++)
  42.                 scanf("%d",&v[i]);
  43.  
  44.         int q;cin>>q;for(int i=0;i<q;i++)
  45.         {
  46.              int l,r;
  47.              scanf("%d %d",&l,&r);
  48.              node tmp;
  49.              tmp.l=l-1;
  50.              tmp.r=r-1;
  51.              tmp.id=i;
  52.              u[i]=tmp;
  53.         }
  54.  
  55.          sort(u,u+q,cool);
  56.  
  57.          int st=0,e=0;fuk=1;cnt[v[0]]++;
  58.  
  59.         for(int i=0;i<q;i++)
  60.         {
  61.             int l=u[i].l;
  62.             int r=u[i].r;
  63.            // cout<<l<<" "<<r<<" "<<st<<" "<<e<<" "<<fuk<<endl;
  64.  
  65.             while(st<l)
  66.             {
  67.                 cnt[v[st]]--;
  68.                 if(cnt[v[st]]==0)
  69.                  fuk--;
  70.                  st++;
  71.             }
  72.             while(st>l)
  73.             {
  74.                  st--;
  75.                  cnt[v[st]]++;
  76.                  if(cnt[v[st]]==1)
  77.                  fuk++;
  78.             }
  79.             while(e<r)
  80.             {
  81.                 e++;
  82.                 cnt[v[e]]++;
  83.                 if(cnt[v[e]]==1)
  84.                 fuk++;
  85.             }
  86.             while(e>r)
  87.             {
  88.                cnt[v[e]]--;
  89.                if(cnt[v[e]]==0)
  90.                fuk--;
  91.                e--;
  92.             }            
  93.             ans[u[i].id]=fuk;
  94.         }
  95.  
  96.         for(int i=0;i<q;i++)
  97.             printf("%d\n",ans[i]);
  98.  
  99.      return 0;
  100. }
  101.  
  102.  
  103.  
Time limit exceeded #stdin #stdout 5s 13888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iiNZ9Z
problem DQUERY, based on SPOJ submission 16748206 (C++14), 2016-04-15 16:10:26
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!