Submission #64651

#	Time	Username	Problem	Language	Result	Execution time	Memory
64651		someone_aa	Jousting tournament (IOI12_tournament)	C++17	100 / 100	143 ms	16348 KiB

tournament

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
pair<int,int> intervals[maxn];
int lc[maxn], rc[maxn], n, r, q;
int bit[maxn], curr_intv[maxn], parent[maxn];
int pref[maxn], answ[maxn];

void update(int index, int val) {
    for(int i=index;i<=n;i+=i&(-i)) {
        bit[i] += val;
    }
}

int query(int x) {
    int sum = 0;
    for(int i=x;i>0;i-=i&(-i)) {
        sum += bit[i];
    }
    return sum;
}

void preprocess() {
    for(int i=0;i<=n;i++) {
        lc[i] = i - 1;
        rc[i] = i + 1;
    }
    rc[n] = -1;
}

int bin_search(int val) {
    int index = n;
    if(query(index) < val) return n+1;
    for(int cekor = n; cekor > 0; cekor/=2) {
        while(index - cekor >= 0 && query(index-cekor)>=val) index-=cekor;
    }
    return index;
}

int recursion(int i) {
    if(answ[i] != -1) return answ[i];

    int l = intervals[i].first;
    int r = intervals[i].second;
    int after = r - 1;
    int before = l - 1;
    int cnt = pref[after] - pref[before];

    if(cnt == 0) {
        answ[i] = 1;
        if(parent[i] != -1) answ[i] += recursion(parent[i]);
    }
    else {
        answ[i] = 0;
    }
    return answ[i];
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N; r = R; q = C;
    preprocess();
    for(int i=1;i<=n;i++) update(i, 1);

    memset(curr_intv, -1, sizeof(curr_intv));
    memset(parent, -1, sizeof(parent));
    memset(answ, -1, sizeof(answ));

    for(int i=0;i<q;i++) {
        int l = bin_search(S[i]+1);
        int r = bin_search(E[i]+2) - 1;

        intervals[i] = mp(l, r);

        if(curr_intv[l] != -1) {
            parent[curr_intv[l]] = i;
            curr_intv[l] = i;
        }
        else curr_intv[l] = i;

        //cout<<"Q:"<<i<<" -> "<<l<<" "<<r<<"\n";
        for(int j=rc[l];j<=r && j!=-1;j=rc[j]) {
            //cout<<"upd: "<<j<<"\n";
            // set this value to 0

            if(curr_intv[j] != -1) {
                parent[curr_intv[j]] = i;
                curr_intv[j] = i;
            }
            else curr_intv[j] = i;

            rc[lc[j]] = rc[j];
            lc[rc[j]] = lc[j];

            update(j, -1);
        }
    }


    for(int i=1;i<n;i++) {
        pref[i] = pref[i-1];
        if(K[i-1] > r) pref[i]++;
    }

    int maxm = 0, ind = 1;
    for(int i=0;i<q;i++) {
        int curr = recursion(i);
        if(curr > maxm) {
            maxm = curr;
            ind = intervals[i].first;
        }
        else if(curr == maxm) {
            ind = min(ind, intervals[i].first);
        }
    }
    return ind - 1;
}

/*int arr[maxn], s[maxn], e[maxn];
int main() {
    //ifstream fin("input.txt");

    int n, c, r;
    cin>>n>>c>>r;

    for(int i=0;i<n-1;i++) cin>>arr[i];
    for(int i=0;i<c;i++) cin>>s[i]>>e[i];

    cout<<GetBestPosition(n, c, r, arr, s, e);

    return 0;
}*/

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