Submission #777866

#	Time	Username	Problem	Language	Result	Execution time	Memory
777866		lollipop	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9093 ms	31024 KiB

elephants

//#include "elephants.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#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 YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int NN = 150001 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
//int node[ 200 ][ 4 * NN ] ; 
int n , l , block = 390 , w[ NN ] ;
vector < pair < int , int > > v[ 390 ] ;
pair < int , int > dp[ 400 ][ 900 ] ; 
map < int , vector < int > > ps ; 
void recalculate_dp( int i ){
	 FOR( j , 390 ) dp[ i ][ j ] = { 0 , 0 } ; 
	 if( v[ i ].size() == 0 ) return ;
	 int lst = v[ i ].size() ;
	 for( int j = v[ i ].size() - 1 ; j >= 0 ; j -- ){
	 	int nx = v[ i ][ j ].f + l ; 
	 	while( true ){
	 		if( v[ i ][ lst - 1 ].f > nx ) lst -- ; 
	 		else break ; 
		}
		if( lst == v[ i ].size() ){
			dp[ i ][ j ] = { 1 , nx } ;
		}
		else{
			dp[ i ][ j ].f = 1 + dp[ i ][ lst ].f ;
			dp[ i ][ j ].s = dp[ i ][ lst ].s ; 
		}
	 }
}
void gadaamushave(){
	 vector < int > vu ;
	 FOR( i , 390 ){
	 	for( auto x : v[ i ] ) vu.pb( x.f ) ;
	 	v[ i ].clear() ;
	 }
	 int cnt = 0 , pos = 0 ; 
	 ps.clear() ; 
	 FOR( i , n ){
	   if( cnt == block ){
	   	 cnt = 0 ; pos ++ ;
	   }
	   cnt ++ ; 
	   ps[ vu[ i ] ].pb( pos ) ; 
	   int ss = v[ pos ].size() ;
	   v[ pos ].pb( { vu[ i ] , ss } ) ; 
	 }
	 FOR( i , 390 ){
	 	recalculate_dp( i ) ; 
	 }	 
}
void init(int N, int L, int X[]){
     n = N , l = L ;
     FOR( i , N ) w[ i ] = X[ i ] ;
	 int cnt = 0 , pos = 0 ; 
	 FOR( i , N ){
	   if( cnt == block ){
	   	 cnt = 0 ; pos ++ ;
	   }
	   cnt ++ ; 
	   int ss = v[ pos ].size() ; 
	   v[ pos ].pb( { X[ i ] , ss } ) ; 
	 } 
	 gadaamushave() ;
}
int cc = 0 ; 
int daitrie_pasuxi(){
	int ans = 0 ;
	int lst = -1 ; 
	pair < int , int > p ; 
	FOR( i , 390 ){
	   if( v[ i ].size() == 0 ) continue ; 
	   p = { lst , INT_MAX } ;
	   if( v[ i ][ v[ i ].size() - 1 ].f <= lst ){
	   	   continue ;
	   }
	   p = *upper_bound( v[ i ].begin() , v[ i ].end() , p ) ; 
	   ans = ans + dp[ i ][ p.s ].f ; 
	   lst = dp[ i ][ p.s ].s ; 	
	}
	return ans ;
}
int update(int i , int y){
	if( n == 1 ) return 1 ; 
	cc ++ ; 
	int ss = ps[ w[ i ] ].size() - 1 ; 
	int pos = ps[ w[ i ] ][ ss ] , ww = w[ i ] ; 
	ps[ w[ i ] ].pop_back() ;
	w[ i ] = y ;
	// ar dagaviwydes ps is ganaxleba 
	int tt = 0 ; 
	FOR( i , v[ pos ].size() ){
	   if( tt == 1 ){
	      v[ pos ][ i ].s -- ; 
		  continue ; 		
	   }
	   if( v[ pos ][ i ].f == ww ){
	   	   v[ pos ].erase( v[ pos ].begin() + i ) ;
	   	   i -- ; 
	   	   tt = 1 ; 
	   	   continue ; 
	   }
	}
	recalculate_dp( pos ) ; 
	// axla ipove sad chaagdo
	int lst = 0 ; pos = -1 ;  
	FOR( i , 390 ){
	   if( v[ i ].size() == 0 ) continue ;
	   lst = i ;
	   ss = v[ i ].size() - 1 ;
	   if( v[ i ][ ss ].f >= y ){
	   	  pos = i ; break ; 
	   }
	}
	if( pos == -1 ) pos = lst ; 
	ps[ w[ i ] ].pb( pos ) ;
    ss = v[ pos ].size() ; 
	v[ pos ].pb( { w[ i ] , ss } ) ; 
	for( int j = v[ pos ].size() - 1 ; j > 0 ; j -- ){
		if( v[ pos ][ j - 1 ].f <= v[ pos ][ j ].f ) break ;
	    v[ pos ][ j - 1 ].s ++ ;
		v[ pos ][ j ].s -- ;
		swap( v[ pos ][ j - 1 ] , v[ pos ][ j ] ) ; 	
	} 
	recalculate_dp( pos ) ;
	
	int ans = daitrie_pasuxi() ;
	if( cc == block){
		cc = 0 ; 
		gadaamushave() ; 
	}
	return ans ; 
}



//#define MAX_N 1000000
//#define MAX_M 1000000
//
//static int N,L,M;
//static int X[MAX_N];
//static int ii[MAX_M];
//static int yy[MAX_M];
//
//void read_input()
//{
//  int i;
//  scanf("%d %d %d",&N,&L,&M);
//  for(i=0; i<N; i++)
//	scanf("%d",&X[i]);
//  for(i=0; i<M; i++)
//    scanf("%d %d",&ii[i],&yy[i]);
//}
//
//int main()
//{
//  int i, ans;
//
//  read_input();
//  init(N,L,X);
//  for(i=0; i<M; i++) {
//    ans = update(ii[i],yy[i]);
//    printf("%d\n", ans);
//  }
//  return 0;
//}

Compilation message (stderr)

elephants.cpp: In function 'void recalculate_dp(int)':
elephants.cpp:48:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   if( lst == v[ i ].size() ){
      |       ~~~~^~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  118 |  FOR( i , v[ pos ].size() ){
      |       ~~~~~~~~~~~~~~~~~~~                
elephants.cpp:118:2: note: in expansion of macro 'FOR'
  118 |  FOR( i , v[ pos ].size() ){
      |  ^~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3