제출 #1111749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111749		mariaclara	마상시합 토너먼트 (IOI12_tournament)	C++17	100 / 100	558 ms	36400 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
    for(int t = 0; t < C; t++) {
        int s = S[t], e = E[t];

        for(int i = e; i >= s; i--) {
            edges[N + t].pb(v[i]);
            if(i == s) break;
            v.erase(v.begin() + i);
        }

        v[s] = N + t;
        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;
}

/*
Casos de Teste:
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