Submission #40529

#	Time	Username	Problem	Language	Result	Execution time	Memory
40529		pulgares	Teams (IOI15_teams)	C++14	77 / 100	4069 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(){merge(*l, *r);}
	void merge(stnode& L, stnode& R){sum = L.sum + R.sum;} 
	void upd(int x){sum += x;}
};
typedef stnode* pstnode;

struct ST{
	vector<pstnode> root, all;
	int N;
	void clear(){
		FOR(i,0,all.size()) delete all[i];
		all.clear(); root.clear();
		N=0;
	}
	pstnode new_node(){
		all.pb(new stnode());
		return all.back();
	}
	void init(int n){
		root.pb(new_node());
		N = n;
	}
	void build(){build(root[0],0,N);}
	void build(pstnode v, int l, int r){
		if(r - l < 2){
			v->upd(0); 
			return;
		}
		int M = (l+r)>>1;
		v->l = new_node();
		v->r = new_node();
		build(v->l, l, M); build(v->r, M, r);
		v->merge();
	}

	int query(int x, int y, int ver){
		return query(x,y,root[ver],0,N).sum; 
	}
	stnode query(int x, int y, pstnode v, int l, int r){
		if(x == l && y == r)	return *v;
		int M = (l+r)>>1;
		if(x>=M)	return query(x,y,v->r,M,r);
		if(y<=M)	return query(x,y,v->l,l,M);
		stnode res,ln=query(x, M, v->l, l, M),rn=query(M, y, v->r, M, r);
		return res.merge(ln, rn), res;
	}
    // erase all elements < b in ver (used)
    int erase(int b, int ver){
        root.pb(erase(b, root[ver], root[0], 0, N));
        return root.size()-1;
    }
    pstnode erase(int b, pstnode v, pstnode emptyv, int l, int r){
        if(r<=b) return emptyv;
		int M = (l+r)>>1;
        pstnode u = new_node();
        if(b<=M){
            u->r = v->r;
            u->l = erase(b, v->l, emptyv->l, l, M);
        }else{
            u->l = emptyv->l;
            u->r = erase(b, v->r, emptyv->r, M, r);
        }
        u->merge();
        return u;
    }
    int K;
    bool bs(int k, int ver, int &usedver){
        K = k;
        //debug(k);
        if(root[ver]->sum - root[usedver]->sum < K) 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 K==0;    
    }
    // we are always in nodes were we have enough.
    pstnode bs(pstnode v, pstnode usedv, int l, int r){
        int lft = v->sum - usedv->sum;
        if(lft == K){
            K=0;
            return v;
        }
        pstnode u = new_node();
        u->sum = usedv->sum;
        if(r-l==1){
            u->sum += K;
            K=0;
            return u;
            
        }
        int M = (l+r)>>1;
        int llft = v->l->sum - usedv->l->sum;
        if(llft >= K){
            u->r = usedv->r;
            u->l = bs(v->l, usedv->l, l, M);
        }else{
            K -= llft;
            u->l = v->l;
            u->r = bs(v->r, usedv->r, M, r);
        }
        u->merge();
        return u;
    }

	int update(int p, int x, int ver){
		root.pb(update(p, x, root[ver], 0, N));
		return root.size()-1;
	}
	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;
	}
    void print(int ver){
        print(root[ver], 0, N);
    }
    void print(pstnode v, int l, int r){
        if(r-l==1){
            printf("%d, ", v->sum);
            return;
        }
        int M = (l+r)>>1;
        print(v->l, l, M);
        print(v->r, M, r);
    }
};

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

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

int M, K[MAXN];


int solve(){
    int ans = 1;
    sort(K, K+M);
    int usedrt = 0;
    FOR(i,0,M && ans){
        //debug(K[i]);
        //debug(st.root[strt[K[i]]]->sum);
        //debug(st.root[usedrt]->sum);
        usedrt = st.erase(K[i], usedrt);
        //debug(st.root[usedrt]->sum);
        ans &= st.bs(K[i], strt[K[i]], usedrt);
        //debug(st.root[usedrt]->sum);
        //debug("print",K[i]);
        //st.print(strt[K[i]]);
        //printf("\nprint used\n");
        //st.print(usedrt);
        //printf("\n");

    }

    return ans;
}

void pre(){
    FOR(i,0,N){
        AtoB[A[i]].pb(B[i]);
        BtoB[B[i]]++;
    }
    st.init(N+5);
    st.build();
    strt.pb(0);
    FOR(i,1,N+1){
        int nxt = strt.back();
        //debug(i);
        //debug(st.root[nxt]->sum);
        for(int b : AtoB[i]) nxt = st.update(b, 1, nxt);
        if(BtoB[i-1]) nxt = st.update(i-1, -BtoB[i-1], nxt);
        //debug(BtoB[i-1]);
        strt.pb(nxt);
        //debug(st.root[strt[i]]->sum);
    }
}


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 member function 'int ST::erase(int, int)':
teams.cpp:117: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 member function 'bool ST::bs(int, int, int&)':
teams.cpp:140: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 member function 'int ST::update(int, int, int)':
teams.cpp:175: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 '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