Submission #583353

#	Time	Username	Problem	Language	Result	Execution time	Memory
583353		Jomnoi	Jousting tournament (IOI12_tournament)	C++17	100 / 100	131 ms	28096 KiB

tournament

#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

const int MAX_N = 1e5 + 5;

int table[MAX_N][20];
vector <int> addSeg[MAX_N], removeSeg[MAX_N];

struct Node {
    int al, ar, mi, ma;
    int prior, size;
    Node *l, *r;
    Node(const int &al_, const int &ar_) : al(al_), ar(ar_), mi(al_), ma(ar_), prior(rand()), size(1), l(NULL), r(NULL) {}
};

int get_size(Node *t) {
    if(t == NULL) {
        return 0;
    }
    return t->size;
}

void combine(Node *&t, Node *l, Node *r) {
    if(l == NULL or r == NULL) {
        return void(t = (l != NULL ? l : r));
    }

    t->size = l->size + r->size;
    t->mi = l->mi;
    t->ma = r->ma;
}

void update(Node *t) {
    if(t == NULL) {
        return;
    }
 
    t->size = 1;
    t->mi = t->al;
    t->ma = t->ar;
    combine(t, t->l, t);
    combine(t, t, t->r);
}

void merge(Node *&t, Node *l, Node *r) {
    if(l == NULL or r == NULL) {
        t = (l != NULL ? l : r);
    }
    else if(l->prior > r->prior) {
        merge(l->r, l->r, r);
        t = l;
    }
    else {
        merge(r->l, l, r->l);
        t = r;
    }
    update(t);
}

void split(Node *t, Node *&l, Node *&r, int key, int add = 0) {
    if(t == NULL) {
        return void(l = r = NULL);
    }

    int cur_key = get_size(t->l) + add;
    if(key <= cur_key) {
        split(t->l, l, t->l, key, add);
        r = t;
    }
    else {
        split(t->r, t->r, r, key, cur_key + 1);
        l = t;
    }
    update(t);
}

int get_max(int l, int r) {
    int j = log2(r - l);
    return max(table[l][j], table[r - (1<<j)][j]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    Node *root = NULL;
    for(int i = 0; i < N; i++) {
        merge(root, root, new Node(i, i));
    }
    for(int c = 0; c < C; c++) {
        Node *left, *mid, *right;
        split(root, left, mid, S[c]);
        split(mid, mid, right, E[c] - S[c] + 1);

        Node *tmp = new Node(mid->mi, mid->ma);
        S[c] = mid->mi;
        E[c] = mid->ma;

        merge(left, left, tmp);
        merge(root, left, right);
    }

    for(int i = 0; i < N - 1; i++) {
        table[i][0] = K[i];
    }
    for(int j = 1; j < 20; j++) {
        for(int i = 0; i + (1<<j) - 1 < N; i++) {
            table[i][j] = max(table[i][j - 1], table[i + (1<<(j - 1))][j - 1]);
        }
    }

    for(int c = 0; c < C; c++) {
        addSeg[S[c]].push_back(c);
        removeSeg[E[c] + 1].push_back(c);
    }

    int max_win = -1, best_pos = 0, cnt_win = 0;
    for(int p = 0; p < N; p++) {
        for(auto i : removeSeg[p]) {
            if(get_max(S[i], E[i]) < R) {
                cnt_win--;
            }
        }
        for(auto i : addSeg[p]) {
            if(get_max(S[i], E[i]) < R) {
                cnt_win++;
            }
        }

        if(DEBUG) {
            cout << p << " : " << cnt_win << endl;
        }

        if(max_win < cnt_win) {
            max_win = cnt_win;
            best_pos = p;
        }
    }
    return best_pos;
}

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