oj.uz

Submission #577617

# Submission time Handle Problem Language Result Execution time Memory
577617 2022-06-15T06:36:59 Z lollipop Poklon (COCI17_poklon) C++17
84 / 140
 5000 ms 19944 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 block ;
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 ] ] -- ; 
}
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); 
    int n , q ;
    cin >> n >> q ; 
    FOR( i , n ) cin >> 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:63:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<stu>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for( int i = 0 ; i < v.size() ; i ++ ){
      |                      ~~^~~~~~~~~~

Subtask #1
84.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 4 ms 340 KB Output is correct
4 Correct 30 ms 660 KB Output is correct
5 Correct 2365 ms 4504 KB Output is correct
6 Correct 3136 ms 4532 KB Output is correct
7 Execution timed out 5064 ms 8332 KB Time limit exceeded
8 Execution timed out 5050 ms 15020 KB Time limit exceeded
9 Execution timed out 5056 ms 16136 KB Time limit exceeded
10 Execution timed out 5036 ms 19944 KB Time limit exceeded