Submission #1026621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026621		onbert	Jousting tournament (IOI12_tournament)	C++17	100 / 100	83 ms	14168 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, maxN = 4e5 + 5, lgn = 18;
int n, q, a[maxn];

int seg[maxN][2];
void build(int id, int l, int r, int i) {
    if (l==r) {
        seg[id][i] = 1;
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid, i); build(id*2+1, mid+1, r, i);
    seg[id][i] = seg[id*2][i] + seg[id*2+1][i];
}
void update(int id, int l, int r, int findl, int findr, int i) {
    if (findr<l || r<findl) return;
    if (findl<=l && r<=findr && seg[id][i]==0) return;
    if (l==r) {
        seg[id][i] = 0;
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, i); update(id*2+1, mid+1, r, findl, findr, i);
    seg[id][i] = seg[id*2][i] + seg[id*2+1][i];
}
int qry(int id, int l, int r, int val, int lhs, int i) {
    if (l==r) return l;
    int mid = (l+r)/2;
    if (seg[id*2][i] + lhs >= val) return qry(id*2, l, mid, val, lhs, i);
    return qry(id*2+1, mid+1, r, val, lhs + seg[id*2][i], i);
}

int st[maxn][lgn];
void buildst() {
    for (int i=0;i<n;i++) for (int j=0;j<lgn;j++) st[i][j] = -1;
    for (int i=n-1;i>=0;i--) {
        st[i][0] = a[i];
        for (int j=1;j<lgn;j++) {
            if (i + (1<<j) - 1 > n-1) break;
            st[i][j] = max(st[i][j-1], st[i + (1<<(j-1))][j-1]);
        }
    }
}
int mx(int l, int r) {
    int lg = log2(r-l+1);
    return max(st[l][lg], st[r - (1<<lg) + 1][lg]);
}

int fen[maxn];
void update1(int id, int val) {
    while (id<maxn) {
        fen[id] += val;
        id += (id & -id);
    } 
}
int qry1(int id) {
    int val = 0;
    while (id >= 1) {
        val += fen[id];
        id -= (id & -id);
    }
    return val;
}

int GetBestPosition(int N, int Q, int R, int *K, int *S, int *E) {
    n = N, q = Q;
    for (int i=0;i<n-1;i++) a[i] = K[i];
    build(1, 0, n-1, 0); build(1, 0, n-1, 1);
    buildst();
    for (int i=0;i<Q;i++) {
        int l = qry(1, 0, n-1, S[i]+1, 0, 0);
        int r = qry(1, 0, n-1, E[i]+1, 0, 1);
        if (mx(l, r-1) < R) {
            update1(l+1, 1);
            update1(r+2, -1);
        }
        update(1, 0, n-1, l+1, r, 0);
        update(1, 0, n-1, l, r-1, 1);
    }
    int mx = -1, ans = -1;
    for (int i=0;i<n;i++) {
        int val = qry1(i+1);
        if (val > mx) mx = val, ans = i;
    }
    return ans;
}

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