oj.uz

Submission #40534

# Submission time Handle Problem Language Result Execution time Memory
40534 2018-02-04T10:04:36 Z pulgares Teams (IOI15_teams) C++14
77 / 100
 4000 ms 524288 KB 
//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;
    vector<stnode> nodes;
	int N;
	void clear(){
		all.clear(); root.clear();
        nodes.clear();
	}
	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];
    }

    // erase all elements < b in ver (used)
    inline int erase(int b, int ver){
        root.pb(erase(b, root[ver], root[0], 0, N));
        return root.size()-1;
    }
    inline 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;
    inline 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.
    inline 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;
    }

	inline int update(int p, int x, int ver){
		root.pb(update(p, x, root[ver], 0, N));
		return root.size()-1;
	}
	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;
	}
};

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

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 ni = st.all.size();
    //debug(ni);
    int usedrt = 0;
    FOR(i,0,M && ans){
        usedrt = st.erase(K[i], usedrt);
        ans &= st.bs(K[i], strt[K[i]], usedrt);
    }
    FOR(i,ni,st.all.size()) delete st.all[i];
    st.all.resize(ni);
    

    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

teams.cpp: In member function 'int ST::erase(int, int)':
teams.cpp:99: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:122: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:157: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:190:26: warning: conversion to 'int' from 'std::vector<stnode*>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int ni = st.all.size();
                          ^
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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12152 KB Output is correct
2 Correct 11 ms 12268 KB Output is correct
3 Correct 11 ms 12444 KB Output is correct
4 Correct 11 ms 12444 KB Output is correct
5 Correct 11 ms 12444 KB Output is correct
6 Correct 11 ms 12456 KB Output is correct
7 Correct 11 ms 12456 KB Output is correct
8 Correct 11 ms 12456 KB Output is correct
9 Correct 11 ms 12456 KB Output is correct
10 Correct 12 ms 12564 KB Output is correct
11 Correct 11 ms 12564 KB Output is correct
12 Correct 15 ms 12652 KB Output is correct
13 Correct 12 ms 12652 KB Output is correct
14 Correct 11 ms 12652 KB Output is correct
15 Correct 12 ms 12692 KB Output is correct
16 Correct 11 ms 12692 KB Output is correct
17 Correct 11 ms 12692 KB Output is correct
18 Correct 11 ms 12692 KB Output is correct
19 Correct 11 ms 12692 KB Output is correct
20 Correct 11 ms 12692 KB Output is correct
21 Correct 11 ms 12692 KB Output is correct
22 Correct 11 ms 12692 KB Output is correct
23 Correct 11 ms 12692 KB Output is correct
24 Correct 11 ms 12692 KB Output is correct
25 Correct 12 ms 12692 KB Output is correct
26 Correct 11 ms 12692 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 127656 KB Output is correct
2 Correct 283 ms 128788 KB Output is correct
3 Correct 273 ms 129976 KB Output is correct
4 Correct 283 ms 132216 KB Output is correct
5 Correct 131 ms 132216 KB Output is correct
6 Correct 134 ms 132216 KB Output is correct
7 Correct 132 ms 132216 KB Output is correct
8 Correct 131 ms 132216 KB Output is correct
9 Correct 234 ms 138936 KB Output is correct
10 Correct 193 ms 138936 KB Output is correct
11 Correct 136 ms 138936 KB Output is correct
12 Correct 126 ms 138936 KB Output is correct
13 Correct 177 ms 138936 KB Output is correct
14 Correct 203 ms 138936 KB Output is correct
15 Correct 262 ms 138936 KB Output is correct
16 Correct 256 ms 138936 KB Output is correct
17 Correct 142 ms 138936 KB Output is correct
18 Correct 144 ms 138936 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 145456 KB Output is correct
2 Correct 282 ms 147024 KB Output is correct
3 Correct 510 ms 154248 KB Output is correct
4 Correct 303 ms 154248 KB Output is correct
5 Correct 246 ms 154248 KB Output is correct
6 Correct 233 ms 154248 KB Output is correct
7 Correct 138 ms 154248 KB Output is correct
8 Correct 209 ms 154248 KB Output is correct
9 Correct 246 ms 158792 KB Output is correct
10 Correct 370 ms 158792 KB Output is correct
11 Correct 329 ms 158792 KB Output is correct
12 Correct 287 ms 158792 KB Output is correct
13 Correct 393 ms 158792 KB Output is correct
14 Correct 559 ms 158792 KB Output is correct
15 Correct 383 ms 160968 KB Output is correct
16 Correct 366 ms 162316 KB Output is correct
17 Correct 243 ms 162316 KB Output is correct
18 Correct 284 ms 162316 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4126 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -