Submission #784599

#	Time	Username	Problem	Language	Result	Execution time	Memory
784599		lollipop	Teams (IOI15_teams)	C++17	13 / 100	1900 ms	380436 KiB

teams

#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 ; 
	int smm =0 ;
	FOR( i , M ) smm += K[ i ] ;
	if( smm > n ) return 0 ; 
    FOR( i , M ) dp[ i ] = 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{
	   dp[ i ] = opa( *(--se.end() ) , 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 ] << " " << mn << "  " << 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 (stderr)

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:144:45: warning: declaration of 'p' shadows a global declaration [-Wshadow]
  144 |           pair < int , pair < int , int > > p ;
      |                                             ^
teams.cpp:37:20: note: shadowed declaration is here
   37 | pair < int , int > p[ 12 * N ] ;
      |                    ^
teams.cpp:155:18: warning: declaration of 'x' shadows a previous local [-Wshadow]
  155 |              int x = p.s.s ;
      |                  ^
teams.cpp:142:12: note: shadowed declaration is here
  142 |        int x = k[ i ] ;
      |            ^
teams.cpp:163:8: warning: left operand of comma operator has no effect [-Wunused-value]
  163 |      X - -1 , Y = i ;
      |      ~~^~~~
teams.cpp:173:13: warning: declaration of 'x' shadows a previous local [-Wshadow]
  173 |         int x = *(--se.end() ) ;
      |             ^
teams.cpp:142:12: note: shadowed declaration is here
  142 |        int x = k[ i ] ;
      |            ^
teams.cpp:142:12: warning: unused variable 'x' [-Wunused-variable]
teams.cpp:161:13: warning: variable 'Y' set but not used [-Wunused-but-set-variable]
  161 |     int X , Y ;
      |             ^

• Subtask 1: 0 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23