Submission #1111762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111762		mariaclara	Jousting tournament (IOI12_tournament)	C++17	100 / 100	430 ms	36940 KiB

tournament

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back 
#define fr first 
#define sc second

int anc[20][MAXN], l_range[MAXN], r_range[MAXN], val[MAXN], niv[MAXN], seg[2*MAXN];
vector<int> edges[MAXN];

void dfs(int x) {
    for(int viz : edges[x]) {
        niv[viz] = niv[x] + 1;
        dfs(viz);
        anc[0][viz] = x;
        l_range[x] = min(l_range[x], l_range[viz]);
        r_range[x] = max(r_range[x], r_range[viz]);
    }
}

void build(int node, int l, int r) {
    if(l == r) {
        seg[node] = val[l];
        return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    seg[node] = max(seg[2*node], seg[2*node + 1]);
}

void update(int node, int l, int r, int ind, int new_val) {
    if(l == r) {
        seg[node] = new_val;
        return;
    }
    int mid = (l+r)/2;
    if(ind <= mid) update(2*node, l, mid, ind, new_val);
    else update(2*node + 1, mid+1, r, ind, new_val);
    seg[node] = max(seg[2*node], seg[2*node + 1]);
}

int query(int node, int l, int r, int p, int q) {
    if(r < p or q < l) return -1;
    if(p <= l and r <= q) return seg[node];
    int mid = (l+r)/2;
    return max(query(2*node,l,mid,p,q), query(2*node+1,mid+1,r,p,q));
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    vector<int> v(N);
    for(int i = 0; i < N; i++) v[i] = l_range[i] = r_range[i] = i;

    // Unica parte em O(N²) é a construção das arestas

    const int Sqrt = 300;
    vector<vector<int>> groups;
    groups.pb({0});

    for(int i = 1; i < N; i++) {
        if(sz(groups.back()) == Sqrt) groups.pb({i});
        else groups.back().pb(i);
    }

    for(int t = 0; t < C; t++) {
        int s = S[t], e = E[t], add = 0;

        for(int G = 0, tam = 0; G < sz(groups); G++) {
            int l_inter = max(s, tam), r_inter = min(e, tam + sz(groups[G]) - 1);
            int ini_size = sz(groups[G]);
            if(l_inter > r_inter) { tam += ini_size; continue;}
            l_inter -= tam;
            r_inter -= tam;

            for(int i = r_inter; i >= l_inter; i--) {
                edges[N + t].pb(groups[G][i]);
                if(!add and i == l_inter) break;
                groups[G].erase(groups[G].begin() + i);
            }

            if(!add) groups[G][l_inter] = N + t, add = 1;
            tam += ini_size;
        }

        l_range[N + t] = N-1;
    }

    dfs(N + C - 1); // construindo os intervalos
    anc[0][N + C - 1] = N + C - 1;

    for(int bit = 1; bit <= 16; bit++) // construindo os ancestrais
        for(int i = 0; i < N + C; i++) 
            anc[bit][i] = anc[bit-1][anc[bit-1][i]];

    val[0] = R;
    for(int i = 1; i < N; i++) val[i] = K[i-1];

    build(1, 0, N-1); // seg construida

    int ans = -1, num_ans = -1;
    for(int i = 0; i < N; i++) { // dar swap em i e i+1

        int x = i;
        for(int bit = 16; bit >= 0; bit--) {
            if(query(1, 0, N-1, l_range[anc[bit][x]], r_range[anc[bit][x]]) == R) {
                x = anc[bit][x];
            }
        }
        
        if(niv[i] - niv[x] > num_ans) num_ans = niv[i] - niv[x], ans = i;

        if(i == N-1) break;

        swap(val[i], val[i+1]);
        update(1, 0, N-1, i, val[i]);
        update(1, 0, N-1, i+1, val[i+1]);
    }
    
    return ans;
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/

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