fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int blk=1500,ar[500005],qq[500005],
  4. cnt[500005],val[500005],res,tot ;
  5. struct str{
  6.     int a,b,c ;
  7. }qr[500003] ;
  8. bool comp(str s1 , str s2)
  9. {
  10.     int a=s1.a/blk , b = s2.a/blk ;
  11.     if(a!=b) return a<b ;
  12.     return s1.b<s2.b ;
  13. }
  14. void add(int id)
  15. {
  16.     int k=ar[id] ;
  17.     if(cnt[k]==val[k]) tot-- ;
  18.     cnt[k]++ ;
  19.     if(cnt[k]==1) res++ ;
  20.     if(cnt[k]==val[k]) tot++ ;
  21. }
  22. void rmove(int id)
  23. {
  24.     int k=ar[id] ;
  25.     if(cnt[k]==val[k]) tot-- ;
  26.     cnt[k]-- ;
  27.     if(cnt[k]==0) res-- ;
  28.     if(cnt[k]==val[k]) tot++ ;
  29. }
  30. int32_t main()
  31. {
  32.     int n,m ;
  33.     scanf("%d%d",&n,&m) ;
  34.     for(int i = 0 ; i < n ; i++) scanf("%d",&ar[i]) ;
  35.     for(int i = 1 ; i <= m ; i++) scanf("%d",&val[i]) ;
  36.     int q ; cin>>q;
  37.     for(int i = 0 ; i < q ; i++)
  38.     {
  39.         int l,r;cin>>l>>r ; l-- ; r-- ;
  40.         qr[i].a=l;qr[i].b=r;qr[i].c=i ;
  41.     }
  42.     sort(qr,qr+q,comp) ;
  43.   //  for(int i = 0 ; i < q ; i++)
  44.   // cout<<qr[i].a<<" "<<qr[i].b<<" "<<qr[i].c<<endl ;
  45.   //cout<<endl ;
  46.     int ml=0,mr=-1 ; res=0;tot=0;
  47.     for(int i = 0 ; i < q ; i++)
  48.     {
  49.         int l=qr[i].a , r=qr[i].b ; //l-- ; r-- ;
  50.         //cout<<l<<" "<<r<<endl ;
  51.         while(mr<r){mr++ ; add(mr) ; }
  52.         while(mr>r){rmove(mr) ; mr-- ; }
  53.         while(ml<l){rmove(ml) ; ml++ ; }
  54.         while(ml>l){ml-- ; add(ml) ; }
  55.        // cout<<ml<<" "<<mr<<endl ;
  56.        // cout<<res<<" rt "<<tot<<endl ;
  57.      //   cout<<endl ;
  58.          qq[qr[i].c]=(res==tot) ;
  59.     }
  60.     for(int i = 0 ; i < q ; i++)
  61.        printf("%d\n",qq[i]) ;
  62. }
  63. /*
  64. 8 4
  65. 2 2 1 4 4 2 4 4
  66. 1 2 3 4
  67. 12
  68. 1 8
  69. 1 2
  70. 3 3
  71. 3 8
  72. 1 4
  73. 1 5
  74. 1 7
  75. 1 3
  76. 4 8
  77. 6 8
  78. 1 6
  79. 2 5
  80. */
  81.  
Success #stdin #stdout 0s 4272KB
comments (?)
stdin
copy 
8 4
2 2 1 4 4 2 4 4
1 2 3 4
6
1 2
1 5
1 3
2 8
3 3
5 8
stdout
copy 
1
0
1
1
1
0
https://ideone.com/rGUDfM
language:
C++14 (gcc 8.3)
created:
4 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!