oj.uz

Submission #577627

# Submission time Handle Problem Language Result Execution time Memory
577627 2022-06-15T06:48:05 Z lollipop Poklon (COCI17_poklon) C++17
140 / 140
 1737 ms 20988 KB 
#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
#define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
using namespace std ;
const int mod1 =  1000000007 ;
const int mod = 998244353 ; 
const int N = 2e5 + 10 ; 
//map < int , int > ma , ma1 ;
int ma[ 500005 ] ; 
int block = 800 ;
struct stu{
     int f ;
     int s ;
     int indx ; 
};
int qu[ 500005 ] ; 
bool sortby( stu p , stu p1 ){
  if( p.f / block == p1.f / block ) return p.s < p1.s ;
  else return ( p.f / block ) < ( p1.f / block ) ;
}
int ans = 0 ; 
int a[ 500005 ] ; 
void addR( int i ){
     if( ma[ a[ i ] ] == 2 ) ans -- ; 
     if( ma[ a[ i ] ] == 1 ) ans ++ ; 
     ma[ a[ i ] ] ++ ;
}
void delR( int i ){
     if( ma[ a[ i ] ] == 3 ) ans ++ ;
     if( ma[ a[ i ] ] == 2 ) ans -- ;
     ma[ a[ i ] ] -- ;   
}
void addL( int i ){
     if( ma[ a[ i ] ] == 2 ) ans -- ; 
     if( ma[ a[ i ] ] == 1 ) ans ++ ; 
     ma[ a[ i ] ] ++ ;
}
void delL( int i ){
     if( ma[ a[ i ] ] == 3 ) ans ++ ;
     if( ma[ a[ i ] ] == 2 ) ans -- ;
     ma[ a[ i ] ] -- ; 
}
map < int , int > mu ;
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); 
    int n , q ;
    cin >> n >> q ; 
   set < int > se ;
    FOR( i , n ){
       cin >> a[ i + 1 ] ;
      se.insert( a[ i + 1 ] ) ;
    }
    int st = 0 ;
  while( se.size() > 0 ){
    int x = *se.begin() ;
    mu[ x ] = st ;
    st ++ ;
    se.erase( se.begin() ) ;  
  }
    FOR( i , n ) a[ i + 1 ] = mu[ a[ i + 1 ] ] ; 
    vector < stu > v ;
  //  block = ( n / sqrt( q ) ) ;
    FOR( i , q ){
      int x , y ; cin >> x >> y ;
      v.pb( { x , y , i } ) ; 
    } 
     sort( v.begin() , v.end() , sortby ) ;
    int l = 1 , r = 0 ;
    for( int i = 0 ; i < v.size() ; i ++ ){
      int L = v[ i ].f ; 
      int R = v[ i ].s ;
      while( l < L ){
         delL( l ) ;
         l ++ ;
      }
      while( l > L ){
         l -- ;
         addL( l ) ;
      }
      while( R > r ){
        r ++ ;  
        addR( r ) ; 
      }
      while( R < r ){
        delR( r ) ;
        r -- ;
      }
      qu[ v[ i ].indx ] = ans ; 
    }
  FOR( i , q ) cout << qu[ i ] << "\n" ;
}

Compilation message

poklon.cpp:10: warning: "FOR" redefined
   10 | #define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
      | 
poklon.cpp:9: note: this is the location of the previous definition
    9 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
      | 
poklon.cpp:11: warning: "FOR" redefined
   11 | #define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
      | 
poklon.cpp:10: note: this is the location of the previous definition
   10 | #define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
      | 
poklon.cpp: In function 'int main()':
poklon.cpp:77:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<stu>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for( int i = 0 ; i < v.size() ; i ++ ){
      |                      ~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 664 KB Output is correct
5 Correct 168 ms 4596 KB Output is correct
6 Correct 173 ms 4524 KB Output is correct
7 Correct 486 ms 8740 KB Output is correct
8 Correct 835 ms 15104 KB Output is correct
9 Correct 1264 ms 16944 KB Output is correct
10 Correct 1737 ms 20988 KB Output is correct