oj.uz

Submission #777867

# Submission time Handle Problem Language Result Execution time Memory
777867 2023-07-09T19:39:58 Z lollipop Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 25820 KB 
//#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 ][ 1500 ] ; 
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 1 ms 3028 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 1 ms 3028 KB Output is correct
7 Correct 434 ms 5640 KB Output is correct
8 Correct 470 ms 6288 KB Output is correct
9 Correct 960 ms 10668 KB Output is correct
10 Correct 989 ms 10560 KB Output is correct
11 Correct 1006 ms 10596 KB Output is correct
12 Correct 1112 ms 10732 KB Output is correct
13 Correct 1004 ms 10564 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 1 ms 3028 KB Output is correct
7 Correct 434 ms 5640 KB Output is correct
8 Correct 470 ms 6288 KB Output is correct
9 Correct 960 ms 10668 KB Output is correct
10 Correct 989 ms 10560 KB Output is correct
11 Correct 1006 ms 10596 KB Output is correct
12 Correct 1112 ms 10732 KB Output is correct
13 Correct 1004 ms 10564 KB Output is correct
14 Correct 484 ms 6540 KB Output is correct
15 Correct 771 ms 7160 KB Output is correct
16 Correct 1763 ms 10872 KB Output is correct
17 Correct 2400 ms 13668 KB Output is correct
18 Correct 2280 ms 13704 KB Output is correct
19 Correct 1972 ms 13760 KB Output is correct
20 Correct 2238 ms 13756 KB Output is correct
21 Correct 2280 ms 13832 KB Output is correct
22 Correct 2132 ms 13800 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 1 ms 3028 KB Output is correct
7 Correct 434 ms 5640 KB Output is correct
8 Correct 470 ms 6288 KB Output is correct
9 Correct 960 ms 10668 KB Output is correct
10 Correct 989 ms 10560 KB Output is correct
11 Correct 1006 ms 10596 KB Output is correct
12 Correct 1112 ms 10732 KB Output is correct
13 Correct 1004 ms 10564 KB Output is correct
14 Correct 484 ms 6540 KB Output is correct
15 Correct 771 ms 7160 KB Output is correct
16 Correct 1763 ms 10872 KB Output is correct
17 Correct 2400 ms 13668 KB Output is correct
18 Correct 2280 ms 13704 KB Output is correct
19 Correct 1972 ms 13760 KB Output is correct
20 Correct 2238 ms 13756 KB Output is correct
21 Correct 2280 ms 13832 KB Output is correct
22 Correct 2132 ms 13800 KB Output is correct
23 Execution timed out 9018 ms 25820 KB Time limit exceeded
24 Halted 0 ms 0 KB -