제출 #1066084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066084		ArthuroWich	마상시합 토너먼트 (IOI12_tournament)	C++17	100 / 100	227 ms	38908 KiB

tournament

//#include "tournament.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
struct node {
    int p = -1, b = 0, w = 1;
    vector<int> c = {};
};
node t[200005];
int timer, ra, v = 0, succ[200005][20], depth[200005];
void calc(int i) {
    for (int j : t[i].c) {
        depth[j+1] = depth[i+1]+1;
        calc(j);
    }
    for (int j : t[i].c) {
        t[i].b += t[j].b;
    }
}
void update0(int i, int l, int f) {
    if (l == i) {
        return;
    }
    if (f) {
        t[i].b--;
    }
    update0(t[i].p, l, 1);
}
void update1(int i, int l, int f) {
    if (l == i) {
        return;
    }
    if (f) {
        t[i].b++;
    }
    update1(t[i].p, l, 1);
}
void initsucc() {
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < 200000; i++) {
            succ[i][j] = succ[succ[i][j-1]][j-1];
        }
    }
}
int kthjump(int a, int k) {
    for (int j = 0; j < 20; j++) {
        if (k & (1 << j)) {
            a = succ[a][j];
        }
    }
    return a;
}
int lca(int a, int b) {
    a++;
    b++;
    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    b = kthjump(b, depth[b]-depth[a]);
    if (a == b) {
        return a-1;
    }
    for (int j = 19; j >= 0; j--) {
        if (succ[a][j] != succ[b][j]) {
            a = succ[a][j];
            b = succ[b][j];
        }
    }
    return succ[a][0]-1;
}
void trav(int i) {
    i++;
    for (int j = 19; j >= 0; j--) {
        if (succ[i][j]-1 < 0) {
            continue;
        }
        if (t[succ[i][j]-1].b == 0) {
            v += (1<<j);
            i = succ[i][j];
        }
    }
}
int GetBestPosition(int n, int m, int r, int k[], int S[], int E[]) {
    ra = r;
    indexed_set e;
    timer = n;
    int ans = 0, ind = -1;
    for (int i = 0; i < n; i++) {
        e.insert({i, i});
    }
    for (int j = 0; j < 20; j++) {
        for (int i = 0; i <= 200000; i++) {
            succ[i][j] = 0;
        }
    }
    for (int i = 0; i < n-1; i++) {
        if (k[i] > r) {
            t[i+1].b = 1;
        }
    }
    for (int i = 0; i < m; i++) {
        int le = E[i]-S[i]+1;
        set<pair<int, int>> todel;
        pair<int, int> c;
        auto ind = e.find_by_order(S[i]);
        int l = INT_MAX;
        t[timer].w = 1;
        while(le--) {
            c = *ind;
            todel.insert(c);
            l = min(l, c.first);
            t[timer].c.push_back(c.second);
            t[c.second].p = timer;
            succ[c.second+1][0] = timer+1;
            ind++;
        }
        for (auto c : todel) {
            e.erase(c);
        }
        e.insert({l, timer});
        timer++;
    }
    initsucc();
    int root = timer-1;
    calc(root);
    trav(0);
    ans = v;
    ind = 0;
    for (int i = 1; i < n; i++) {
        swap(t[i-1].b, t[i].b);
        if (t[i].b != t[i-1].b) {
            int l = lca(i-1, i);
            update0(i, l, 0);
            update1(i-1, l, 0);
        }
        v = 0;
        trav(i);
        if (v > ans) {
            ans = v;
            ind = i;
        }
    }
    return ind;
}

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