oj.uz

Submission #784602

# Submission time Handle Problem Language Result Execution time Memory
784602 2023-07-16T10:52:16 Z lollipop Teams (IOI15_teams) C++17
100 / 100
 2912 ms 380636 KB 
#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 N = 2e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "teams.h"
vector < int > v[ N ] , v1[ N ] ;
int n ; 
int cc = 2 ;
int node[ 12 * N ] ;
pair < int , int > p[ 12 * N ] ;
void build( int v , int vl , int vr ){
	 if( vl == vr ){
	 	node[ v ] = 0 ;
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 p[ v ].f = cc ; cc ++ ;
	 p[ v ].s = cc ; cc ++ ;
	 build( p[ v ].f , vl , vm ) ;
	 build( p[ v ].s , vm + 1 , vr ) ;
	 return ; 
}
int app[ N ] ;
void update( int v , int old , int vl , int vr , int pos , int val ){
	 if( vl == vr ){
	 	node[ v ] = node[ old ] + val ; 
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm >= pos ){
	 	 p[ v ].s = p[ old ].s ;
	 	 p[ v ].f = cc ; cc ++ ;
	 	 update( p[ v ].f , p[ old ].f , vl , vm , pos , val ) ; 
	 }
	 else{
	 	p[ v ].f = p[ old ].f ;
	 	p[ v ].s = cc ; cc ++ ;
	 	update( p[ v ].s , p[ old ].s , vm + 1 , vr , pos , val ) ;
	 }
	 node[ v ] = node[ p[ v ].f ] + node[ p[ v ].s ] ;
	 return ; 
}
int get( int v , int vl , int vr , int l , int r ){
	if( l > r ) return 0 ;
	if( vl == l && vr == r ){
		return node[ v ] ; 
	}
	int vm = ( vl + vr ) / 2 ;
	int a = get( p[ v ].f , vl , vm , l , min( r , vm ) ) ;
	int b = get( p[ v ].s , vm + 1 , vr , max( l , vm + 1 ) , r ) ;
	return a + b ; 
}
map < int , int > pp[ N ] ; 
void init(int n1, int A[], int B[]){
	 n = n1 ; 
	 FOR( i , n ){
	 	v[ A[ i ] ].pb( B[ i ] ) ;
	 	pp[ A[ i ] ][ B[ i ] ] ++ ;
	 }
	 build( 1 , 1 , n ) ; 
	 app[ 0 ] = 1 ; 
	 for( int j = 1 ; j <= n ; j ++ ){
	 	int lst = app[ j - 1 ] ; 
	 	for( auto x : pp[ j ] ){
	 		cc ++ ; 
	 		int ls = cc - 1 ; 
	 		update( cc - 1 , lst , 1 , n , x.f , x.s ) ; 
	 		lst = ls ; 
		}
		app[ j ] = lst ;  
	 }
}
int dp[ N ] , k[ N ] , bn[ N ] ;
int get_when( int x , int y ){
	if( k[ x ] == k[ y ] ) return INT_MAX ; 
	int l = k[ y ] , r = n + 1 ;
	while( l < r ){
		int mid = ( l + r ) / 2 ;
		if( mid == n + 1 ) return INT_MAX ;
		int aa = get( app[ mid ] , 1 , n , mid , n ) - get( app[ k[ x ] ] , 1 , n , mid , n ) ; 
		int bb = get( app[ mid ] , 1 , n , mid , n ) - get( app[ k[ y ] ] , 1 , n , mid , n ) ; 
		int a = dp[ x ] + aa ; 
		int b = dp[ y ] + bb ; 
		if( a <= b ){
			r = mid ; 
		}
		else l = mid + 1 ; 
	} 
	if( l > r ) l = INT_MAX ;
	return l ; 
}
int opa( int x , int y ){
    int cc = 0 ; 
	if( x != -1 ) 
    cc = get( app[ k[ x ] ] , 1 , n , k[ y ] , n ) ;
	int aa = get( app[ k[ y ] ] , 1 , n , k[ y ] , n ) - cc ; 
	int cic = 0 ;
	if( x != -1 ) cic = dp[ x ] ; 
    int a = cic + aa ; 
	a -= k[ y ] ; 	
	return a ; 
}
int can(int M, int K[]){

	sort( K , K + M ) ;	
	FOR( i , M ) k[ i ] = K[ i ] , bn[ i ] = 0 , dp[ i ] = 0 ; 
	int smm =0 ;
	FOR( i , M ) smm += K[ i ] ;
	if( smm > n ) return 0 ; 
    set < int > se ;
    set < pair < int , pair < int , int > > > lst ;
    int mn = INT_MAX ; 
    FOR( i , M ){
       int x = k[ i ] ;
       while( true ){
       	  pair < int , pair < int , int > > p ;
       	  if( lst.size() == 0 ) break ;
       	  p = *(lst.begin()) ;
       	  if( p.f > k[ i ] ) break ;       	  
		  lst.erase( lst.begin() ) ; 
       	  if( bn[ p.s.s ] == 1 ) continue ;
		  if( bn[ p.s.f ] == 1 ) continue ; 
       	  bn[ p.s.f ] = 1 ;
       	  se.erase( se.find( p.s.f ) ) ;
       	  if( se.size() == 0 ) break ;
       	  if( *( -- se.end() ) != p.s.s ){
       	     int x = p.s.s ;
		     int y = *se.upper_bound( x ) ;
			 int tm = get_when( x , y ) ;
			 lst.insert( { tm , { y , x } } ) ;	
		  }
	   }
	   int X , Y ; 
	   if( se.size() == 0 ){
	   	X - -1 , Y = i ; 
	   	   dp[ i ] = opa( -1 , i ) ;
	   }	
	   else{
	   	int cc = *( --se.end() ) ;
	   dp[ i ] = min(  opa( cc, i ) , opa( -1 , i ) ) ; 
	    X = *(--se.end() ) ; 
	    Y = i ; 
	   }
	  // cout << i << " " << dp[ i ] << endl ;
	   if( se.size() != 0 ){
	   	   int x = *(--se.end() ) ;
	   	   int y = i ; 
	   	   int tm = get_when( x , y ) ;
	   	   lst.insert( { tm , { y , x } } ) ;
	   }
	   se.insert( i ) ;
	   mn = min( mn , dp[ i ] ) ; 
//	   cout << i << " " << K[ i ] << " " << dp[ i ] << "  " << X << " " << Y << endl ;
	}
    if( mn < 0 ) return 0 ;
    return 1 ; 
}
//static char buffer[1024];
//static int currentChar = 0;
//static int charsNumber = 0;
//
//
//
//int main() {
//  int N;
//  cin >> N ; 
//  int *A = (int *)malloc(sizeof(int) * (unsigned int)N);
//  int *B = (int *)malloc(sizeof(int) * (unsigned int)N);
//  for (int i = 0; i < N; ++i) {
//    cin >> A[ i ] ;
//    cin >> B[ i ] ; 
//  }
//  init(N, A, B);
//  int Q;
//  cin >> Q ; 
//  for (int i = 0; i < Q; ++i) {
//    int M;
//    cin >> M ; 
//    int *K = (int *)malloc(sizeof(int) * (unsigned int)M);
//    for (int j = 0; j < M; ++j) {
//      cin >> K[ j ] ; 
//    }
//    cout << can( M , K ) << "\n" ; 
//  }
//  return 0;
//}

Compilation message

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:38:17: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   38 | void build( int v , int vl , int vr ){
      |             ~~~~^
teams.cpp:33:16: note: shadowed declaration is here
   33 | vector < int > v[ N ] , v1[ N ] ;
      |                ^
teams.cpp: In function 'void update(int, int, int, int, int, int)':
teams.cpp:51:18: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   51 | void update( int v , int old , int vl , int vr , int pos , int val ){
      |              ~~~~^
teams.cpp:33:16: note: shadowed declaration is here
   33 | vector < int > v[ N ] , v1[ N ] ;
      |                ^
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:70:14: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   70 | int get( int v , int vl , int vr , int l , int r ){
      |          ~~~~^
teams.cpp:33:16: note: shadowed declaration is here
   33 | vector < int > v[ N ] , v1[ N ] ;
      |                ^
teams.cpp: In function 'int opa(int, int)':
teams.cpp:120:9: warning: declaration of 'cc' shadows a global declaration [-Wshadow]
  120 |     int cc = 0 ;
      |         ^~
teams.cpp:35:5: note: shadowed declaration is here
   35 | int cc = 2 ;
      |     ^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:143:45: warning: declaration of 'p' shadows a global declaration [-Wshadow]
  143 |           pair < int , pair < int , int > > p ;
      |                                             ^
teams.cpp:37:20: note: shadowed declaration is here
   37 | pair < int , int > p[ 12 * N ] ;
      |                    ^
teams.cpp:154:18: warning: declaration of 'x' shadows a previous local [-Wshadow]
  154 |              int x = p.s.s ;
      |                  ^
teams.cpp:141:12: note: shadowed declaration is here
  141 |        int x = k[ i ] ;
      |            ^
teams.cpp:162:8: warning: left operand of comma operator has no effect [-Wunused-value]
  162 |      X - -1 , Y = i ;
      |      ~~^~~~
teams.cpp:166:10: warning: declaration of 'cc' shadows a global declaration [-Wshadow]
  166 |      int cc = *( --se.end() ) ;
      |          ^~
teams.cpp:35:5: note: shadowed declaration is here
   35 | int cc = 2 ;
      |     ^~
teams.cpp:173:13: warning: declaration of 'x' shadows a previous local [-Wshadow]
  173 |         int x = *(--se.end() ) ;
      |             ^
teams.cpp:141:12: note: shadowed declaration is here
  141 |        int x = k[ i ] ;
      |            ^
teams.cpp:141:12: warning: unused variable 'x' [-Wunused-variable]
teams.cpp:160:13: warning: variable 'Y' set but not used [-Wunused-but-set-variable]
  160 |     int X , Y ;
      |             ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 188108 KB Output is correct
2 Correct 82 ms 188200 KB Output is correct
3 Correct 80 ms 188164 KB Output is correct
4 Correct 82 ms 188132 KB Output is correct
5 Correct 80 ms 188208 KB Output is correct
6 Correct 80 ms 188264 KB Output is correct
7 Correct 81 ms 188164 KB Output is correct
8 Correct 86 ms 188164 KB Output is correct
9 Correct 88 ms 188180 KB Output is correct
10 Correct 81 ms 188176 KB Output is correct
11 Correct 80 ms 188172 KB Output is correct
12 Correct 79 ms 188204 KB Output is correct
13 Correct 81 ms 188136 KB Output is correct
14 Correct 83 ms 188124 KB Output is correct
15 Correct 80 ms 188112 KB Output is correct
16 Correct 80 ms 188160 KB Output is correct
17 Correct 80 ms 188136 KB Output is correct
18 Correct 80 ms 188200 KB Output is correct
19 Correct 82 ms 188216 KB Output is correct
20 Correct 81 ms 188168 KB Output is correct
21 Correct 83 ms 188168 KB Output is correct
22 Correct 81 ms 188204 KB Output is correct
23 Correct 85 ms 188212 KB Output is correct
24 Correct 82 ms 188164 KB Output is correct
25 Correct 87 ms 188176 KB Output is correct
26 Correct 80 ms 188176 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 218960 KB Output is correct
2 Correct 148 ms 218996 KB Output is correct
3 Correct 164 ms 219032 KB Output is correct
4 Correct 199 ms 231484 KB Output is correct
5 Correct 90 ms 192460 KB Output is correct
6 Correct 89 ms 193404 KB Output is correct
7 Correct 93 ms 193400 KB Output is correct
8 Correct 88 ms 193296 KB Output is correct
9 Correct 101 ms 197132 KB Output is correct
10 Correct 94 ms 194848 KB Output is correct
11 Correct 85 ms 192964 KB Output is correct
12 Correct 92 ms 193092 KB Output is correct
13 Correct 98 ms 198412 KB Output is correct
14 Correct 133 ms 206252 KB Output is correct
15 Correct 136 ms 215192 KB Output is correct
16 Correct 134 ms 215288 KB Output is correct
17 Correct 91 ms 193968 KB Output is correct
18 Correct 96 ms 194128 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 219552 KB Output is correct
2 Correct 561 ms 219352 KB Output is correct
3 Correct 236 ms 222400 KB Output is correct
4 Correct 198 ms 231448 KB Output is correct
5 Correct 569 ms 192948 KB Output is correct
6 Correct 573 ms 193964 KB Output is correct
7 Correct 585 ms 194100 KB Output is correct
8 Correct 563 ms 194064 KB Output is correct
9 Correct 116 ms 197044 KB Output is correct
10 Correct 141 ms 195388 KB Output is correct
11 Correct 157 ms 193620 KB Output is correct
12 Correct 462 ms 193932 KB Output is correct
13 Correct 635 ms 199408 KB Output is correct
14 Correct 637 ms 221648 KB Output is correct
15 Correct 748 ms 216116 KB Output is correct
16 Correct 726 ms 216144 KB Output is correct
17 Correct 672 ms 194724 KB Output is correct
18 Correct 692 ms 194652 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1788 ms 356348 KB Output is correct
2 Correct 1812 ms 356320 KB Output is correct
3 Correct 971 ms 362056 KB Output is correct
4 Correct 804 ms 380636 KB Output is correct
5 Correct 1305 ms 209948 KB Output is correct
6 Correct 1291 ms 210968 KB Output is correct
7 Correct 1314 ms 210996 KB Output is correct
8 Correct 1308 ms 211024 KB Output is correct
9 Correct 224 ms 229628 KB Output is correct
10 Correct 215 ms 211860 KB Output is correct
11 Correct 486 ms 209972 KB Output is correct
12 Correct 1185 ms 211500 KB Output is correct
13 Correct 1707 ms 239152 KB Output is correct
14 Correct 2912 ms 361372 KB Output is correct
15 Correct 2243 ms 315328 KB Output is correct
16 Correct 2168 ms 315288 KB Output is correct
17 Correct 1769 ms 219004 KB Output is correct
18 Correct 1648 ms 219036 KB Output is correct