Submission #109569

#	Time	Username	Problem	Language	Result	Execution time	Memory
109569		nvmdava	Jousting tournament (IOI12_tournament)	C++17	100 / 100	63 ms	4100 KiB

tournament

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

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

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

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

inline int finder(int val){
    int res = 0;
    int id = 0;
    for(int i = 16; i >= 0; i--){
        if(id + (1 << i) <= N && 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) {
    int i;
    ::N = N;
    for(i = 1; i <= N; i++)
        p[i] = i + 1;
    for(i = 1; i < BIG; i++){
        fen[i] = i & -i;
        in[i] = 1;
    }

    for(i = 1; i < N; i++){
        if(K[i - 1] > R) last[i] = i;
        else last[i] = last[i - 1];
    }
    last[N] = last[N - 1];
    for(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(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