Submission #1111215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111215		manhlinh1501	Jousting tournament (IOI12_tournament)	C++17	0 / 100	28 ms	4176 KiB

tournament

#include<bits/stdc++.h>
#include <algorithm>
#define maxN 100010
#define maxBinN 131072
#define MAX(a,b) ((a>b)?a:b)
#define MIN(a,b) ((a<b)?a:b)
using namespace std;

int it[maxBinN << 1], bin;
int alive[maxBinN << 1];

struct Layer {
    int add, i;
    inline bool operator < (const Layer &c) const {
        return i < c.i;
    }
} wins[maxN << 1];

int renumber(int x, int s, int e, int remain) {
    int m = (s + e) >> 1;
    if( x >= bin ) return m;
    if( alive[x << 1] >= remain ) return renumber(x << 1, s, m, remain);
    return renumber(x << 1 | 1, m + 1, e, remain - alive[x << 1]);
}

int st, ed;
void kill(int x, int s, int e) {
    if( e < st || ed < s ) return;
    else if( st <= s && e <= ed ) alive[x] = 0;
    else {
        int m = (s + e) >> 1;
        kill(x << 1, s, m);
        kill(x << 1 | 1, m + 1, e);
        alive[x] = MIN( alive[x << 1] + alive[x << 1 | 1], alive[x] );
    }
}

int getMax(int x, int s, int e) {
    if( e < st || ed < s ) return -1;
    else if( st <= s && e <= ed ) return it[x];
    else {
        int m = (s + e) >> 1, t, tt;
        t = getMax(x << 1, s, m);
        tt = getMax(x << 1 | 1, m + 1, e);
        return MAX(t, tt);
    }
}

int GetBestPosition(int n, int rn, int my, int *a, int *S, int *E) {
    bin = 1;
    while( n > bin ) bin <<= 1;
    for(int i = 0; i < n - 1; i++) it[bin + i] = a[i];
    for(int i = 0; i < n; i++) alive[bin + i] = 1;
    for(int i = bin - 1; i; i--) {
        it[i] = MAX(it[i << 1], it[i << 1 | 1]);
        alive[i] = alive[i << 1] + alive[i << 1 | 1];
    }

    int m = 0;
    for(int r = 0; r < rn; r++) {
        S[r] = renumber(1, 0, bin - 1, S[r] + 1);
        E[r] = renumber(1, 0, bin - 1, E[r] + 1);
        st = S[r] + 1, ed = E[r];
        kill(1, 0, bin - 1);
        st = S[r], ed = E[r] - 1;
        if( my > getMax(1, 0, bin - 1)) {
//            printf("%d %d %d\n", S[r] + 1, E[r] + 1, getMax(1, 0, bin - 1) + 1);
            wins[m].i = S[r], wins[m++].add = 1;
            wins[m].i = E[r], wins[m++].add = -1;
        }
    }

    int acc = 0, best = 0, ans = 0;
    sort(wins, wins + m);
    for(int i = 0; i < m; i++) {
        acc += wins[i].add;
//        printf("%d %d\n", wins[i].i + 1, wins[i].add);
        if( acc > best ) best = acc, ans = wins[i].i;
    }

    return ans;
}

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