fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int SIZE = (int)1e5+10;
  5. int f[2*SIZE], a[2*SIZE];			// f = frequency array, a = input array
  6. vector <unordered_set <int> > S( 2*SIZE );
  7. int ans, sq;
  8.  
  9. bool cmp( tuple <int, int, int>& a, tuple <int, int, int>& b ) {
  10.  
  11.     if( get<0>(a)/sq != get<0>(b)/sq )
  12.         return get<0>(a) < get<0>(b);
  13.     return get<1>(a) < get<1>(b);
  14. }
  15.  
  16. void extend( int index ) {
  17.  
  18. 	int v = a[index];
  19.     if( f[v] > 0 )
  20.         S[f[v]].erase( v );
  21.     f[v]++;
  22.     if( f[v] > 0 )
  23.         S[f[v]].insert( v );
  24.  
  25.     if( f[v] > ans )
  26.         ans += 1;
  27. }
  28.  
  29. void shrink( int index ) {
  30.  
  31. 	int v = a[index];
  32.     if( f[v] > 0 )
  33.         S[f[v]].erase( v );
  34.     f[v]--;
  35.     if( f[v] > 0 )
  36.         S[f[v]].insert( v );
  37.  
  38.     if( ans > 0 && S[ans].size() == 0 )
  39.         ans -= 1;
  40. }
  41.  
  42. int main( int argc, char *argv[] ) {
  43.  
  44.     int n, q, L, R;
  45.     while( scanf("%d", &n) && n != 0 ) {
  46.  
  47. 		// clear the data structures
  48.         memset(f, 0, sizeof f);
  49.         for( int i = 0; i < 2*SIZE; i++ )
  50.             S[i].clear();
  51.  
  52.         scanf("%d", &q);
  53.         sq = sqrt(n);
  54.         for( int i = 0; i < n; i++ ) {
  55.             scanf("%d", &a[i]);
  56.             if( a[i] < 0 )				// -x will be transformed to SIZE + x
  57.                 a[i] = abs(a[i]) + SIZE;
  58.         }
  59.  
  60.         vector <tuple <int, int, int> > query(q);
  61.         int answer[q];
  62.  
  63.         for( int i = 0; i < q; i++ ) {
  64.             scanf("%d %d", &L, &R);
  65.             query[i] = make_tuple( L-1, R-1, i );	// 0-based indexing
  66.         }
  67.  
  68.         sort( query.begin(), query.end(), cmp );
  69.  
  70.         int currentL = get<0>( query[0] );
  71.         int currentR = currentL;
  72.         f[a[currentL]]++;
  73.         S[f[a[currentL]]].insert( a[currentL] );
  74.         ans = 1;
  75.  
  76.         for( int i = 0; i < q; i++ ) {
  77.  
  78.             L = get<0>( query[i] ), R = get<1>( query[i] );
  79.             while( currentL < L ) {
  80.  
  81.                 shrink( currentL );
  82.                 ++currentL;
  83.             }
  84.  
  85.             while( currentL > L ) {
  86.  
  87.                 --currentL;
  88.                 extend( currentL );
  89.             }
  90.  
  91.             while( currentR < R ) {
  92.  
  93.                 ++currentR;
  94.                 extend( currentR );
  95.             }
  96.  
  97.             while( currentR > R ) {
  98.  
  99.                 shrink( currentR );
  100.                 --currentR;
  101.             }
  102.             answer[ get<2>(query[i]) ] = ans;
  103.         }
  104.         for( int i = 0; i < q; i++ )
  105.             printf("%d\n", answer[i]);
  106.     }
  107.     return 0;
  108. }
Success #stdin #stdout 0.02s 14348KB
comments (?)
stdin
copy 
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
stdout
copy 
1
4
3
https://ideone.com/E9kNVs
language:
C++14 (gcc 8.3)
created:
6 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!