Submission #711763

#	Time	Username	Problem	Language	Result	Execution time	Memory
711763		lukameladze	Jousting tournament (IOI12_tournament)	C++14	100 / 100	104 ms	5324 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
const int MX = 3e5 + 5;
int n, tree[4 * MX], a[MX],tree_f[MX];
void build(int node, int le, int ri) {
    if (le == ri) {
        tree[node] = a[le];
        return ;
    }
    int mid = (le + ri) / 2;
    build(2 * node, le,mid);
    build(2 * node + 1, mid + 1, ri);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
int getmax(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) return tree[node];
    int mid = (le + ri) / 2;
    return max(getmax(2 * node, le, mid, start, end), getmax(2 * node + 1, mid + 1, ri, start,end));
}
void update(int idx, int val) {
    for (int i = idx; i < MX; i+=i&(-i)) {
        tree_f[i] += val;
    }
}
int getans(int idx) {
    int pas = 0;
    for (int i = idx; i > 0; i-=i&(-i)) {
        pas += tree_f[i];
    }
    return pas;
}
int get(int idx) {
    int le = 1, ri = n, ans = n + 1;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        if (getans(mid) >= idx) {
            ans = mid;
            ri = mid - 1;
        } else le = mid + 1;
    }
    return ans;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N;
    for(int i = 0; i < C; i++) {
        S[i]++; E[i]++;
    }
    for (int i = 1; i <= n - 1; i++) {
        a[i] = K[i - 1];
    }
    build(1,1,n - 1);
    for (int i = 1; i <= n; i++) {
        update(i, 1);
    }
    vector <int> pr; 
    pr = vector <int> (n + 5, 0);
    for (int i = 0; i < C; i++) {
        int st = get(S[i]);
        int nd = get(E[i] + 1) - 1;
        vector <int> v;
        for (int j = S[i] + 1; j <= E[i]; j++) {
            v.pb(get(j));
        }
        for (int x : v) update(x, -1);
        if (getmax(1,1,n - 1,st, nd - 1) < R) {
            pr[st]++; pr[nd]--;
        }
    }
    int res = -1, ret = 0;
    for (int i = 1; i <= n - 1; i++) {
        pr[i] += pr[i - 1];
        if (pr[i] > res) {
            res = pr[i];
            ret = i;
        }
    }
    return ret - 1;
}

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