Submission #592368

#	Time	Username	Problem	Language	Result	Execution time	Memory
592368		snasibov05	Jousting tournament (IOI12_tournament)	C++14	100 / 100	397 ms	40604 KiB

tournament

#include <vector>
 
using namespace std;
 
#define pb push_back
 
const int lg = 25;
 
vector<int> l, r;
vector<vector<int>> pr;
vector<vector<int>> ed;
 
struct SegmentTree{
    vector<int> t;
    SegmentTree(int n){
        t.resize(4*n+5);
    }
 
    void update(int v, int tl, int tr, int idx, int k){
        if (tl == tr){
            t[v] = k;
            return;
        }
 
        int tm = (tl + tr) / 2;
        if (idx <= tm) update(v*2, tl, tm, idx, k);
        else update(v*2+1, tm+1, tr, idx, k);
 
        t[v] = t[v*2] + t[v*2+1];
    }
 
    int idx(int v, int tl, int tr, int k){
        if (tl == tr){
            return tl;
        }
 
        int tm = (tl + tr) / 2;
        if (t[v*2] > k) return idx(v*2, tl, tm, k);
        else return idx(v*2+1, tm+1, tr, k - t[v*2]);
    }
 
    int sum(int v, int tl, int tr, int ql, int qr){
        if (tl == ql && tr == qr){
            return t[v];
        }
 
        int tm = (tl + tr) / 2;
        int res = 0;
 
        if (ql <= tm) res += sum(v*2, tl, tm, ql, min(qr, tm));
        if (qr > tm) res += sum(v*2+1, tm+1, tr, max(ql, tm+1), qr);
 
        return res;
    }
};
 
int buildTree(int n, int c, int*& s, int*& e){
    int idx = n;
    vector<int> cur(n);
 
    SegmentTree tree(n);
 
    for (int i = 0; i < n; ++i) {
        tree.update(1, 0, n-1, i, 1);
        cur[i] = i;
    }
 
    for (int i = 0; i < c; ++i) {
        vector<int> v;
        for (int j = s[i]; j <= e[i]; ++j) {
            int k = tree.idx(1, 0, n-1, j);
            v.pb(k);
            ed[idx].pb(cur[k]);
        }
 
        for (int j = s[i]; j <= e[i]; ++j) {
            cur[v[j - s[i]]] = idx;
            if (j != s[i]) tree.update(1, 0, n-1, v[j - s[i]], 0);
        }
 
        idx++;
    }
 
    return idx-1;
}
 
void dfs(int v, int p){
    pr[0][v] = p;
    for (int i = 1; i < lg; ++i) {
        if (pr[i-1][v] == -1) continue;
        pr[i][v] = pr[i-1][pr[i-1][v]];
    }
 
    l[v] = v;
    for (auto x : ed[v]){
        dfs(x, v);
        l[v] = min(l[v], l[x]);
        r[v] = max(r[v], r[x]);
    }
    if (r[v] == 0) r[v] = l[v];
}
 
void init(int n){
    ed.resize(2*n);
    l.resize(2*n);
    r.resize(2*n);
    pr.resize(lg);
    for (int i = 0; i < lg; ++i) {
        pr[i].resize(2*n);
        pr[i].assign(2*n, -1);
    }
}
 
int GetBestPosition(int n, int c, int rk, int *k, int *s, int *e) {
    init(n);
 
    int m = buildTree(n, c, s, e);
 
    int mx = 0, ans = 0;
 
    dfs(m, -1);
 
    SegmentTree tree(n);
    for (int i = 0; i < n - 1; ++i) {
        if (k[i] > rk) tree.update(1, 0, n-1, i+1, 1);
    }
 
    for (int i = 0; i < n; ++i) {
 
        int cur = i;
        int res = 0;
 
        for (int j = lg-1; j >= 0; --j) {
            if (pr[j][cur] == -1) continue;
            int p = pr[j][cur];
            int x = tree.sum(1, 0, n-1, l[p], r[p]);
            if (x == 0) cur = pr[j][cur], res += (1 << j);
        }
 
        if (res > mx) mx = res, ans = i;
 
        if (i == n-1) continue;
 
        tree.update(1, 0, n-1, i+1, 0);
        if (k[i] > rk) tree.update(1, 0, n-1, i, 1);
    }
 
    return ans;
 
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51