Submission #40543

#	Time	Username	Problem	Language	Result	Execution time	Memory
40543		pulgares	Teams (IOI15_teams)	C++14	77 / 100	4157 ms	524288 KiB

teams

//marico el que lo lea
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <assert.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;

void fastIO() {
	std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}

#define FOR(i,f,t) for(int i=f; i<(int)t; i++)
#define FORR(i,f,t) for(int i=f; i>(int)t; i--)
#define FORE(i,c) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define all(obj) obj.begin(), obj.end()
#define ms(obj, val) memset(obj, val, sizeof(obj))
#define ms2(obj, val, sz) memset(obj, val, sizeof(obj[0])*sz)

#define fst first
#define snd second

template<typename T, typename U> inline void mnze(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void mxze(T &x, U y) { if(x < y) x = y; }

void _scan( int &x ) { scanf("%d",&x); }
void _scan( long long &x ) { scanf("%lld",&x); }
void _scan( double &x ) { scanf("%lf",&x); }
void _scan( char &x ) { scanf(" %c",&x); }
void _scan( char *x ) { scanf("%s",x); }
void scan() {}
template<typename T, typename... U>
void scan( T& head, U&... tail ) { _scan(head); scan(tail...);}

template<typename T> void _dbg(const char* sdbg, T h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename T, typename... U> void _dbg(const char* sdbg, T h, U... t) {
	while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(_i, (x)) cerr <<*_i <<", "; cerr <<"\n"; }}
#define debuga(x, sz) {{cerr <<#x <<" = "; FOR(_i, 0, sz) cerr << x[_i] <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define debuga(x, sz)
#define cerr if(0)cout
#endif


struct stnode{
	int sum; 
	stnode *l=NULL, *r=NULL;
	void merge(){sum = l->sum + r->sum;}
	void upd(int x){sum += x;}
};
typedef stnode* pstnode;


	vector<pstnode> root, all;
    vector<stnode> nodes;
	int N;
	inline void clear(){
		all.clear(); root.clear();
        nodes.clear();
	}
	inline pstnode new_node(){
		all.pb(new stnode());
		return all.back();
	}
	void init(int n){
		root.pb(new_node());
		N = n;
	}
	void build(){
        root[0]->sum = 0;
        root[0]->l=root[0];
        root[0]->r=root[0];
    }

    inline pstnode erase(int b, pstnode v, int l, int r){
        if(r<=b) return root[0];
		int M = (l+r)>>1;
        pstnode u = new_node();
        if(b<=M){
            u->r = v->r;
            u->l = erase(b, v->l, l, M);
        }else{
            u->l = root[0];
            u->r = erase(b, v->r, M, r);
        }
        u->merge();
        return u;
    }
    // erase all elements < b in ver (used)
    inline int erase(int b, int ver){
        root.pb(erase(b, root[ver], 0, N));
        return root.size()-1;
    }
    int KK;
    // we are always in nodes were we have enough.
    inline pstnode bs(pstnode v, pstnode usedv, int l, int r){
        int lft = v->sum - usedv->sum;
        if(lft == KK){
            KK=0;
            return v;
        }
        pstnode u = new_node();
        u->sum = usedv->sum;
        if(r-l==1){
            u->sum += KK;
            KK=0;
            return u;
            
        }
        int M = (l+r)>>1;
        int llft = v->l->sum - usedv->l->sum;
        if(llft >= KK){
            u->r = usedv->r;
            u->l = bs(v->l, usedv->l, l, M);
        }else{
            KK -= llft;
            u->l = v->l;
            u->r = bs(v->r, usedv->r, M, r);
        }
        u->merge();
        return u;
    }
    inline bool bs(int k, int ver, int &usedver){
        KK = k;
        //debug(k);
        if(root[ver]->sum - root[usedver]->sum < KK) return false;
        //debug(root[ver]->sum, root[usedver]->sum);
        root.pb( bs(root[ver], root[usedver], 0, N) );
        usedver = root.size()-1;
        //debug(root[usedver]->sum);
        return KK==0;    
    }

	inline pstnode update(int p, int x, pstnode v, int l, int r){
		pstnode u = new_node();
		if(r - l < 2){
            u->sum = v->sum;
			u->upd(x);
			return u;
		}
		int M = (l+r)>>1;
		u->l = v->l, u->r = v->r;
		if(p < M) u->l = update(p, x, v->l, l, M);
		else u->r = update(p, x, v->r, M, r);
		u->merge();
		return u;
	}
	inline int update(int p, int x, int ver){
		root.pb(update(p, x, root[ver], 0, N));
		return root.size()-1;
	}

///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////

const int MAXN = 5e5+5;
int A[MAXN], B[MAXN], BtoB[MAXN];
vi AtoB[MAXN];
vi strt;

int M, K[MAXN];


int solve(){
    int ans = 1;
    sort(K, K+M);
    int ni = all.size();
    //debug(ni);
    int usedrt = 0;
    FOR(i,0,M && ans){
        int cnt = 1;
        while(i+1<M && K[i] == K[i+1]){
            cnt++;
            i++;
        }
        usedrt = erase(K[i], usedrt);
        ans &= bs(K[i]*cnt, strt[K[i]], usedrt);
    }
    FOR(i,ni,all.size()) delete all[i];
    all.resize(ni);
    

    return ans;
}

void pre(){
    FOR(i,0,N){
        AtoB[A[i]].pb(B[i]);
        BtoB[B[i]]++;
    }
    N++;
    init(N);
    build();
    strt.pb(0);
    FOR(i,1,N){
        int nxt = strt.back();
        if(AtoB[i].size()){
            sort(all(AtoB[i]));
            int b = AtoB[i][0], cnt=1;
            FOR(j,1,AtoB[i].size()){
                if(AtoB[i][j]==b) cnt++;
                else{
                    nxt = update(b, cnt, nxt);
                    cnt=1;
                    b=AtoB[i][j];
                }
            }
            nxt = update(b, cnt, nxt);
        }

        if(BtoB[i-1]) nxt = update(i-1, -BtoB[i-1], nxt);
        strt.pb(nxt);
    }
}


void init(int NN, int *AA, int *BB){
    N=NN;
    FOR(i,0,N) A[i]=AA[i];
    FOR(i,0,N) B[i]=BB[i];
    pre();
}
int can(int MM, int *KK){
    M = MM;
    FOR(i,0,M) K[i]=KK[i];
    return solve();
}

Compilation message (stderr)

teams.cpp: In function 'int erase(int, int)':
teams.cpp:112:28: warning: conversion to 'int' from 'std::vector<stnode*>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         return root.size()-1;
                            ^
teams.cpp: In function 'bool bs(int, int, int&)':
teams.cpp:149:17: warning: conversion to 'int' from 'std::vector<stnode*>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         usedver = root.size()-1;
                 ^
teams.cpp: In function 'int update(int, int, int)':
teams.cpp:170:22: warning: conversion to 'int' from 'std::vector<stnode*>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   return root.size()-1;
                      ^
teams.cpp: In function 'int solve()':
teams.cpp:187:23: warning: conversion to 'int' from 'std::vector<stnode*>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int ni = all.size();
                       ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:243:24: warning: declaration of 'KK' shadows a global declaration [-Wshadow]
 int can(int MM, int *KK){
                        ^
teams.cpp:114:9: note: shadowed declaration is here
     int KK;
         ^
teams.cpp: In function 'void _scan(int&)':
teams.cpp:39:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void _scan( int &x ) { scanf("%d",&x); }
                                      ^
teams.cpp: In function 'void _scan(long long int&)':
teams.cpp:40:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void _scan( long long &x ) { scanf("%lld",&x); }
                                              ^
teams.cpp: In function 'void _scan(double&)':
teams.cpp:41:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void _scan( double &x ) { scanf("%lf",&x); }
                                          ^
teams.cpp: In function 'void _scan(char&)':
teams.cpp:42:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void _scan( char &x ) { scanf(" %c",&x); }
                                        ^
teams.cpp: In function 'void _scan(char*)':
teams.cpp:43:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void _scan( char *x ) { scanf("%s",x); }
                                      ^

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