oj.uz

Submission #777866

# Submission time Handle Problem Language Result Execution time Memory
777866 2023-07-09T19:38:14 Z lollipop Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 31024 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 ][ 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

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 2 ms 3028 KB Output is correct
2 Correct 1 ms 3020 KB Output is correct
3 Correct 1 ms 3020 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 1 ms 3020 KB Output is correct
3 Correct 1 ms 3020 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 2 ms 3028 KB Output is correct
2 Correct 1 ms 3020 KB Output is correct
3 Correct 1 ms 3020 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 449 ms 6452 KB Output is correct
8 Correct 485 ms 7300 KB Output is correct
9 Correct 908 ms 12132 KB Output is correct
10 Correct 1053 ms 11888 KB Output is correct
11 Correct 1030 ms 12076 KB Output is correct
12 Correct 1112 ms 12028 KB Output is correct
13 Correct 1032 ms 11696 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 1 ms 3020 KB Output is correct
3 Correct 1 ms 3020 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 449 ms 6452 KB Output is correct
8 Correct 485 ms 7300 KB Output is correct
9 Correct 908 ms 12132 KB Output is correct
10 Correct 1053 ms 11888 KB Output is correct
11 Correct 1030 ms 12076 KB Output is correct
12 Correct 1112 ms 12028 KB Output is correct
13 Correct 1032 ms 11696 KB Output is correct
14 Correct 479 ms 7968 KB Output is correct
15 Correct 830 ms 8580 KB Output is correct
16 Correct 1788 ms 12728 KB Output is correct
17 Correct 2296 ms 15784 KB Output is correct
18 Correct 2415 ms 15952 KB Output is correct
19 Correct 2097 ms 16056 KB Output is correct
20 Correct 2110 ms 15932 KB Output is correct
21 Correct 2119 ms 15748 KB Output is correct
22 Correct 2016 ms 15328 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 1 ms 3020 KB Output is correct
3 Correct 1 ms 3020 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 449 ms 6452 KB Output is correct
8 Correct 485 ms 7300 KB Output is correct
9 Correct 908 ms 12132 KB Output is correct
10 Correct 1053 ms 11888 KB Output is correct
11 Correct 1030 ms 12076 KB Output is correct
12 Correct 1112 ms 12028 KB Output is correct
13 Correct 1032 ms 11696 KB Output is correct
14 Correct 479 ms 7968 KB Output is correct
15 Correct 830 ms 8580 KB Output is correct
16 Correct 1788 ms 12728 KB Output is correct
17 Correct 2296 ms 15784 KB Output is correct
18 Correct 2415 ms 15952 KB Output is correct
19 Correct 2097 ms 16056 KB Output is correct
20 Correct 2110 ms 15932 KB Output is correct
21 Correct 2119 ms 15748 KB Output is correct
22 Correct 2016 ms 15328 KB Output is correct
23 Execution timed out 9093 ms 31024 KB Time limit exceeded
24 Halted 0 ms 0 KB -