oj.uz

Submission #40529

# Submission time Handle Problem Language Result Execution time Memory
40529 2018-02-04T09:21:25 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;
	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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12024 KB Output is correct
2 Correct 10 ms 12132 KB Output is correct
3 Correct 11 ms 12208 KB Output is correct
4 Correct 13 ms 12356 KB Output is correct
5 Correct 12 ms 12356 KB Output is correct
6 Correct 12 ms 12400 KB Output is correct
7 Correct 11 ms 12736 KB Output is correct
8 Correct 12 ms 12736 KB Output is correct
9 Correct 11 ms 12736 KB Output is correct
10 Correct 11 ms 12736 KB Output is correct
11 Correct 10 ms 12736 KB Output is correct
12 Correct 13 ms 14404 KB Output is correct
13 Correct 12 ms 14404 KB Output is correct
14 Correct 11 ms 14404 KB Output is correct
15 Correct 11 ms 14404 KB Output is correct
16 Correct 10 ms 14404 KB Output is correct
17 Correct 11 ms 14404 KB Output is correct
18 Correct 11 ms 14404 KB Output is correct
19 Correct 11 ms 14404 KB Output is correct
20 Correct 11 ms 14404 KB Output is correct
21 Correct 11 ms 14404 KB Output is correct
22 Correct 11 ms 14404 KB Output is correct
23 Correct 13 ms 14404 KB Output is correct
24 Correct 11 ms 14404 KB Output is correct
25 Correct 11 ms 14404 KB Output is correct
26 Correct 11 ms 14404 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 135444 KB Output is correct
2 Correct 339 ms 136704 KB Output is correct
3 Correct 323 ms 137888 KB Output is correct
4 Correct 329 ms 140028 KB Output is correct
5 Correct 160 ms 140028 KB Output is correct
6 Correct 177 ms 140028 KB Output is correct
7 Correct 146 ms 140028 KB Output is correct
8 Correct 175 ms 140028 KB Output is correct
9 Correct 226 ms 146792 KB Output is correct
10 Correct 209 ms 146792 KB Output is correct
11 Correct 174 ms 146792 KB Output is correct
12 Correct 141 ms 146792 KB Output is correct
13 Correct 181 ms 146792 KB Output is correct
14 Correct 233 ms 146792 KB Output is correct
15 Correct 320 ms 146792 KB Output is correct
16 Correct 283 ms 146792 KB Output is correct
17 Correct 152 ms 146792 KB Output is correct
18 Correct 149 ms 146792 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 153848 KB Output is correct
2 Correct 315 ms 155608 KB Output is correct
3 Correct 666 ms 252060 KB Output is correct
4 Correct 308 ms 252060 KB Output is correct
5 Correct 277 ms 252060 KB Output is correct
6 Correct 270 ms 252060 KB Output is correct
7 Correct 164 ms 252060 KB Output is correct
8 Correct 228 ms 252060 KB Output is correct
9 Correct 233 ms 252060 KB Output is correct
10 Correct 384 ms 258360 KB Output is correct
11 Correct 382 ms 258360 KB Output is correct
12 Correct 392 ms 258360 KB Output is correct
13 Correct 551 ms 261504 KB Output is correct
14 Correct 708 ms 270052 KB Output is correct
15 Correct 488 ms 270052 KB Output is correct
16 Correct 503 ms 270052 KB Output is correct
17 Correct 304 ms 270052 KB Output is correct
18 Correct 340 ms 270052 KB Output is correct

Subtask #4
0 / 23.0

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