Submission #784108

#	Time	Username	Problem	Language	Result	Execution time	Memory
784108		lollipop	Teams (IOI15_teams)	C++17	77 / 100	4057 ms	280312 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 = 1e6 + 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 sm[ N ] ;
int gaq[ N ] ;
int ginda[ N ] ; 	
set < int > se ; 
map < pair < int , int > , int > mu ;
map < int , int > hs ; 
int pipi[ N ] ; 
int can(int M, int K[]){
	sort( K , K + M ) ;
	int smm =0 ;
	hs.clear() ; 
	FOR( i , M ) smm += K[ i ] ;
	if( smm > n ) return 0 ; 
    se.clear() ;
    se.insert( n + 1 ) ; 
    int titu = 0 ; 
 	FOR( i , M ){
		se.insert( K[ i ] ) ;
		hs[ K[ i ] ] = 1 ; 
		sm[ K[ i ] ] = 0 ; 
	}
	int cc = 0 ;
	for( auto x : se ){
		pipi[ titu ] = x ; titu ++ ; 
		gaq[ x ] = cc ; 
		ginda[ cc ] = x ; 
		cc ++ ; 
	}
	ginda[ cc ] = INT_MAX ; 
	se.insert( INT_MAX ) ;
	int tt = 1 ; 
	FOR( i , M ){
		int x = K[ i ] ;
		int rt = app[ x ] ;
		int l = 0 , r = se.size() - 2 ;
		mu.clear() ; 
		while( l <= r ){
			mu[ { l , r } ] ++ ;
			if( mu[ { l , r } ] == 2 ) break ; 
			int mid = ( l + r ) / 2 ;
			int md = mid ; 
		    mid = pipi[ mid ] - 1 ; 
			int sum = get( rt , 1 , n , x , mid ) ;
			int pp = x ; 
			while( true ){
				sum -= sm[ pp ] ;
				pp = ginda[ 1 + gaq[ pp ] ] ; 
				if( pp > mid ) break ; 
			}
			if( sum < x ){
				l = md + 1 ; 
			}
			else r = md ; 
		}
		if( l > r ){
			tt = 0 ; break ; 
		}
		 l = pipi[ l ] - 1 ; 
			int pp = x , ls = x , lf = x ; 
			while( true ){
				int nx = min( l + 1 , ginda[ 1 + gaq[ pp ] ] ) ;
				int xx = get( rt , 1 , n , pp , nx - 1 ) - sm[ pp ] ; 
				if( nx == l + 1 ){
					xx = lf ; 
				} else lf -= xx ; 
				sm[ pp ] += xx ; 
				pp = ginda[ 1 + gaq[ pp ] ] ; 
				if( pp > l ) break ; 
			}	
	}
	return tt ; 
}
//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 can(int, int*)':
teams.cpp:121:6: warning: declaration of 'cc' shadows a global declaration [-Wshadow]
  121 |  int cc = 0 ;
      |      ^~
teams.cpp:35:5: note: shadowed declaration is here
   35 | int cc = 2 ;
      |     ^~
teams.cpp:134:29: warning: conversion from 'std::set<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  134 |   int l = 0 , r = se.size() - 2 ;
      |                   ~~~~~~~~~~^~~
teams.cpp:143:8: warning: declaration of 'pp' shadows a global declaration [-Wshadow]
  143 |    int pp = x ;
      |        ^~
teams.cpp:80:19: note: shadowed declaration is here
   80 | map < int , int > pp[ N ] ;
      |                   ^~
teams.cpp:158:8: warning: declaration of 'pp' shadows a global declaration [-Wshadow]
  158 |    int pp = x , ls = x , lf = x ;
      |        ^~
teams.cpp:80:19: note: shadowed declaration is here
   80 | map < int , int > pp[ N ] ;
      |                   ^~
teams.cpp:158:17: warning: unused variable 'ls' [-Wunused-variable]
  158 |    int pp = x , ls = x , lf = x ;
      |                 ^~

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