Submission #587043

#	Time	Username	Problem	Language	Result	Execution time	Memory
587043		Lucpp	Teams (IOI15_teams)	C++17	100 / 100	2983 ms	154040 KiB

teams

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
const int inf = 1e6;

vector<int> S, L, R;
int upd(int p, int v, int a, int b, int i){
    int j = sz(S);
    S.push_back(S[i]);
    L.push_back(L[i]);
    R.push_back(R[i]);
    if(a==b) S[j] = v;
    else{
        int m = (a+b)/2;
        if(p <= m){
            int k = upd(p, v, a, m, L[i]);
            L[j] = k;
        }
        else{
            int k = upd(p, v, m+1, b, R[i]);
            R[j] = k;
        }
        S[j] = S[L[j]]+S[R[j]];
    }
    return j;
}
int qry(int l, int r, int a, int b, int i){
    if(l <= a && b <= r) return S[i];
    else if(b < l || r < a) return 0;
    int m = (a+b)/2;
    return qry(l, r, a, m, L[i]) + qry(l, r, m+1, b, R[i]);
}

int n, cap;
vector<int> ind, roots;

int f(int l, int r, int cnt){ // maximum i s.t. >= cnt intervals starting between l and r contain i
    int lo = 0, hi = n+1;
    for(int mid = (lo+hi+1)/2; lo<hi; mid=(lo+hi+1)/2){
        if(qry(ind[l]+1, ind[r+1], 1, cap, roots[mid]) >= cnt) lo = mid;
        else hi = mid-1;
    }
    return lo;
}

void init(int _n, int* a, int* b){
    n = _n;
    for(cap = 1; cap <= n+1; cap*=2);
    S.resize(2*cap);
    L.assign(2*cap, -1);
    R.assign(2*cap, -1);
    for(int i = cap-1; i > 0; i--) L[i] = 2*i, R[i] = 2*i+1;

    ind.resize(n+2);
    vector<pair<int, int>> p(n);
    for(int i = 0; i < n; i++) p[i] = {a[i], b[i]};
    sort(p.begin(), p.end());
    int j = 0;
    for(int i = 1; i <= n+1; i++){
        while(j < n && p[j].first < i) j++;
        ind[i] = j;
    }

    vector<pair<int, int>> q(n);
    for(int i = 0; i < n; i++) q[i] = {p[i].second, i};
    sort(q.rbegin(), q.rend());
    j = 0;
    int root = 1;
    roots.resize(n+2);
    for(int i = n+1; i >= 0; i--){
        while(j < n && q[j].first >= i){
            root = upd(q[j].second+1, 1, 1, cap, root);
            j++;
        }
        roots[i] = root;
    }
}


int can(int m, int* K){
    vector<int> v(m);
    for(int i = 0; i < m; i++) v[i] = K[i];
    sort(v.begin(), v.end());
    stack<tuple<int, int, int>> st;
    st.emplace(0, 0, inf);
    for(int x : v){
        while(get<2>(st.top()) < x) st.pop();
        auto [dp, y, good] = st.top();
        int cur = dp-x;
        cur += qry(ind[y+1]+1, ind[x+1], 1, cap, roots[x]);
        if(cur < 0) return 0;
        while(!st.empty()){
            tie(dp, y, good) = st.top();
            if(cur < dp) st.pop();
            else{
                int change = f(y+1, x, cur-dp);
                if(good < change) st.pop();
                else{
                    st.emplace(cur, x, change);
                    break;
                }
            }
        }
    }
    return 1;
}

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