oj.uz

Submission #40544

# Submission time Handle Problem Language Result Execution time Memory
40544 2018-02-04T11:53:50 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 onlyforused;
	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(int o=0){
		all.pb(new stnode());
        all.back()->onlyforused = o;
		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;
        if(v->onlyforused == 0) u = new_node(1);
        else u = v;
        pstnode ul, ur;
        if(b<=M){
            ul = erase(b, v->l, l, M);
            ur = v->r;
        }else{
            ur = erase(b, v->r, M, r);
            ul = root[0];
        }
        u->l = ul; u->r = ur;
        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 where 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;
        if(usedv->onlyforused == 0) u = new_node(1);
        else u = usedv;
        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

teams.cpp: In function 'int erase(int, int)':
teams.cpp:118: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:157: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:178: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:195: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:251:24: warning: declaration of 'KK' shadows a global declaration [-Wshadow]
 int can(int MM, int *KK){
                        ^
teams.cpp:120: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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12028 KB Output is correct
2 Correct 10 ms 12132 KB Output is correct
3 Correct 11 ms 12224 KB Output is correct
4 Correct 11 ms 12288 KB Output is correct
5 Correct 11 ms 12316 KB Output is correct
6 Correct 12 ms 12524 KB Output is correct
7 Correct 11 ms 12524 KB Output is correct
8 Correct 11 ms 12524 KB Output is correct
9 Correct 13 ms 12524 KB Output is correct
10 Correct 11 ms 12524 KB Output is correct
11 Correct 14 ms 12524 KB Output is correct
12 Correct 11 ms 12524 KB Output is correct
13 Correct 11 ms 12620 KB Output is correct
14 Correct 12 ms 12620 KB Output is correct
15 Correct 12 ms 12620 KB Output is correct
16 Correct 11 ms 12620 KB Output is correct
17 Correct 11 ms 12620 KB Output is correct
18 Correct 11 ms 12620 KB Output is correct
19 Correct 11 ms 12708 KB Output is correct
20 Correct 11 ms 12708 KB Output is correct
21 Correct 11 ms 12708 KB Output is correct
22 Correct 11 ms 12708 KB Output is correct
23 Correct 11 ms 12708 KB Output is correct
24 Correct 11 ms 12708 KB Output is correct
25 Correct 12 ms 12708 KB Output is correct
26 Correct 13 ms 12708 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 127752 KB Output is correct
2 Correct 303 ms 128820 KB Output is correct
3 Correct 292 ms 130088 KB Output is correct
4 Correct 301 ms 132116 KB Output is correct
5 Correct 21 ms 132116 KB Output is correct
6 Correct 22 ms 132116 KB Output is correct
7 Correct 26 ms 132116 KB Output is correct
8 Correct 21 ms 132116 KB Output is correct
9 Correct 21 ms 132116 KB Output is correct
10 Correct 23 ms 132116 KB Output is correct
11 Correct 19 ms 132116 KB Output is correct
12 Correct 21 ms 132116 KB Output is correct
13 Correct 58 ms 132116 KB Output is correct
14 Correct 129 ms 132116 KB Output is correct
15 Correct 234 ms 132116 KB Output is correct
16 Correct 244 ms 132116 KB Output is correct
17 Correct 30 ms 132116 KB Output is correct
18 Correct 31 ms 132116 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 145408 KB Output is correct
2 Correct 289 ms 147008 KB Output is correct
3 Correct 567 ms 154364 KB Output is correct
4 Correct 300 ms 154364 KB Output is correct
5 Correct 125 ms 154364 KB Output is correct
6 Correct 108 ms 154364 KB Output is correct
7 Correct 27 ms 154364 KB Output is correct
8 Correct 90 ms 154364 KB Output is correct
9 Correct 19 ms 154364 KB Output is correct
10 Correct 24 ms 154364 KB Output is correct
11 Correct 29 ms 154364 KB Output is correct
12 Correct 88 ms 154364 KB Output is correct
13 Correct 258 ms 154364 KB Output is correct
14 Correct 597 ms 156860 KB Output is correct
15 Correct 316 ms 156860 KB Output is correct
16 Correct 294 ms 156860 KB Output is correct
17 Correct 72 ms 156860 KB Output is correct
18 Correct 72 ms 156860 KB Output is correct

Subtask #4
0 / 23.0

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