Submission #604300

#	Time	Username	Problem	Language	Result	Execution time	Memory
604300		wiwiho	Teams (IOI15_teams)	C++14	100 / 100	1961 ms	266884 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b){ \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

struct Node{
    int v = 0, l = -1, r = -1, tme = 0;
};

vector<Node> st;
vector<int> rt;
int ts = 0;
int n;

int build(int L, int R){
    int id = ts++;
    if(L == R) return id;
    int M = (L + R) / 2;
    st[id].l = build(L, M);
    st[id].r = build(M + 1, R);
    return id;
}

int modify(int x, int L, int R, int oid, int tme){
    int id = oid;
    if(st[id].tme < tme){
        id = ts++;
        st[id] = st[oid];
        st[id].tme = tme;
    }
    if(L == R){
        st[id].v++;
        return id;
    }
    int M = (L + R) / 2;
    if(x <= M) st[id].l = modify(x, L, M, st[id].l, tme);
    else st[id].r = modify(x, M + 1, R, st[id].r, tme);
    st[id].v = st[st[id].l].v + st[st[id].r].v;
    return id;
}

int query(int l, int r, int L, int R, int id){
    //cerr << "query " << l << " " << r << " " << L << " " << R << " " << id << "\n";
    if(l <= L && R <= r){
        //cerr << "OAO\n";
        return st[id].v;
    }
    int M = (L + R) / 2;
    if(r <= M) return query(l, r, L, M, st[id].l);
    else if(l > M) return query(l, r, M + 1, R, st[id].r);
    else return query(l, r, L, M, st[id].l) + query(l, r, M + 1, R, st[id].r);
}

void init(int _n, int A[], int B[]){
    n = _n;
    st.resize(30 * n);
    rt.resize(n + 1);
    rt[0] = build(1, n);

    vector<vector<int>> pos(n + 1);
    for(int i = 0; i < n; i++){
        pos[B[i]].eb(A[i]);
    }
    for(int i = 1; i <= n; i++){
        rt[i] = rt[i - 1];
        for(int j : pos[i]){
            rt[i] = modify(j, 1, n, rt[i], i);
        }
    }
    //cerr << "ok\n";
}

struct seg{
    int l, r, cnt = 0, y = 0, up = n;
};

ostream& operator<<(ostream& o, seg s){
    return o << '(' << s.l << ',' << s.r << ',' << s.cnt << ',' << s.y << ',' << s.up << ')';
}

int can(int m, int _K[]){

    vector<int> K(m);
    for(int i = 0; i < m; i++){
        K[i] = _K[i];
    }
    lsort(K);
    //cerr << "can " << m << " : ";
    //printv(K, cerr);

    deque<seg> dq;
    for(int i : K){
        if(dq.empty()){
            dq.eb(seg({1, i, 0, 0, n}));
        }
        else if(dq.back().r < i){
            dq.eb(seg({dq.back().r + 1, i, 0, 0, dq.back().y - 1}));
        }

        //cerr << "test " << i << "\n";
        //printv(dq, cerr);

        int cnt = 0;
        bool ok = false;
        while(!dq.empty()){
            //cerr << "owo\n";
            seg now = dq.back();
            dq.pob;
            int l = now.l, r = now.r;
            cnt += max(now.cnt, query(l, r, 1, n, rt[i - 1]));
            //cerr << "test " << now << " " << cnt << "\n";
            int need = cnt + i;
            if(query(l, i, 1, n, rt[now.up]) < need) continue;
            ok = true;

            int lr = 1, rr = now.up;
            while(lr < rr){
                //cerr << "binary search " << lr << " " << rr << "\n";
                int mid = (lr + rr) / 2;
                if(query(l, i, 1, n, rt[mid]) >= need) rr = mid;
                else lr = mid + 1;
            }

            dq.eb(seg({l, i, need, lr, now.up}));
            break;
        }
        //cerr << "ok ";
        //printv(dq, cerr);
        if(!ok) return 0;

    }

	return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23