답안 #40537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40537 2018-02-04T10:19:53 Z pulgares Nice sequence (IZhO18_sequence) C++14
컴파일 오류
0 ms 0 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(){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){
        usedrt = erase(K[i], usedrt);
        ans &= bs(K[i], 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()){
            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);
        }

        //for(int b : AtoB[i]) nxt = update(b, 1, nxt);
        if(BtoB[i-1]) nxt = 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

sequence.cpp: In function 'void _scan(int&)':
sequence.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); }
                                      ^
sequence.cpp: In function 'void _scan(long long int&)':
sequence.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); }
                                              ^
sequence.cpp: In function 'void _scan(double&)':
sequence.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); }
                                          ^
sequence.cpp: In function 'void _scan(char&)':
sequence.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); }
                                        ^
sequence.cpp: In function 'void _scan(char*)':
sequence.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); }
                                      ^
/usr/lib/gcc/x86_64-linux-gnu/5/../../../x86_64-linux-gnu/crt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status