Submission #109566

#	Time	Username	Problem	Language	Result	Execution time	Memory
109566		nvmdava	Jousting tournament (IOI12_tournament)	C++17	100 / 100	57 ms	5596 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define BIG 131072

int fen[BIG];
int in[BIG];
int p[BIG];
int last[BIG];
int ans[BIG];
int N;
int find(int v){
    return in[v] == 1 ? v : p[v] = find(p[v]);
}

void upd(int loc){
    while(loc < BIG){
        fen[loc]--;
        loc += loc & -loc;
    }
}

void rangeupd(int l, int r){
    while((l = find(p[l])) <= r){
        in[l] = 0;
        upd(l);
    }
}

int finder(int val){
    int res = 0;
    int id = 0;
    for(int i = 16; i >= 0; i--){
        if(res + fen[id + (1 << i)] < val){
            id += 1 << i;
            res += fen[id];
        }
    }
    return id+1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    for(int i = 1; i <= N; i++){
        p[i] = i + 1;
        in[i] = 1;
    }
    for(int i = 1; i < BIG; i++){
        fen[i] = i & -i;
        in[i] = 1;
    }

    for(int i = 0; i < N - 1; i++){
        last[i + 1] = last[i];
        if(K[i] > R) last[i + 1] = i + 1;
    }
    last[N] = last[N - 1];
    for(int i = 0; i < C; i++){
        S[i] = finder(S[i] + 1);
        E[i] = find(p[finder(E[i] + 1)]) - 1;
        rangeupd(S[i], E[i]);
        if(last[E[i] - 1] < S[i]){
            ans[S[i]]++;
            ans[E[i] + 1]--;
        }
    }
    int ret = 1;
    for(int i = 1; i < BIG; i++){
        ans[i] += ans[i - 1];
        if(ans[i] > ans[ret]) ret = i;
    }
    return ret - 1;
}

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