Submission #1065863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065863		ArthuroWich	Jousting tournament (IOI12_tournament)	C++17	0 / 100	229 ms	16468 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, v = INT_MIN, w = 0;
    vector<int> c = {};
};
node t[300005];
int timer, ra, v = 0;
void calc(int i) {
    for (int j : t[i].c) {
        calc(j);
    }
    for (int j : t[i].c) {
        t[i].v = max(t[i].v, t[j].v);
    }
}
void update(int i) {
    for (int j : t[i].c) {
        t[i].v = max(t[i].v, t[j].v);
    }
    if (t[i].p != -1) {
        update(t[i].p);
    }
}
void trav(int i) {
    if (t[i].w && t[i].v == ra) {
        v++;
    } 
    if (t[i].v != ra) {
        return;
    }
    if (t[i].p) {
        trav(t[i].p);
    }
}
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});
    }
    t[0].v = r;
    for (int i = 0; i < n-1; i++) {
        t[i+1].v = k[i];
    }
    for (int i = 0; i < m; i++) {
        int le = E[i]-S[i]+1;
        set<pair<int, int>> todel;
        pair<int, int> c = {S[i], INT_MIN};
        auto ind = e.find_by_order(e.order_of_key(c));
        int l = INT_MAX;
        while(le--) {
            c = *ind;
            todel.insert(c);
            l = min(l, c.first);
            t[timer].c.push_back(c.second);
            t[c.second].p = timer;
            t[timer].w = 1;
            ind++;
        }
        for (auto c : todel) {
            e.erase(c);
        }
        e.insert({l, timer});
        timer++;
    }
    int root = timer-1;
    calc(root);
    trav(0);
    ans = v;
    ind = 0;
    for (int i = 1; i < n; i++) {
        swap(t[i-1].v, t[i].v);
        update(i-1);
        update(i);
        v = 0;
        trav(i);
        if (v > ans) {
            ans = v;
            ind = i;
        }
    }
    return ind;
}

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