Submission #1098767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098767		esomer	Jousting tournament (IOI12_tournament)	C++17	100 / 100	117 ms	15344 KiB

tournament

#include<bits/stdc++.h>
 
using namespace std;
 
struct segTreeFindRange{
    vector<int> sum, upd;
    int sz;
    void build(int x, int lx, int rx, int n){
        if(rx - lx == 1){
            if(lx < n){
                sum[x] = 1;
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(2 * x + 1, lx, m, n);
        build(2 * x + 2, m, rx, n);
        sum[x] = sum[2 * x + 1] + sum[2 * x + 2];
    }
    void init(int n){
        sz = 1;
        while(sz < n) sz *= 2;
        sum.assign(2 * sz, 0);
        upd.assign(2 * sz, 0);
        build(0, 0, sz, n);
    }
    void push(int x){
        if(!upd[x]) return;
        sum[2 * x + 1] = 0;
        sum[2 * x + 2] = 0;
        upd[2 * x + 1] = 1;
        upd[2 * x + 2] = 1;
        upd[x] = 0;
    }
    void setTo0(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r){
            sum[x] = 0;
            upd[x] = 1;
            return;
        }else if(lx >= r || rx <= l) return;
        int m = (lx + rx) / 2;
        push(x);
        setTo0(l, r, 2 * x + 1, lx, m);
        setTo0(l, r, 2 * x + 2, m, rx);
        sum[x] = sum[2 * x + 1] + sum[2 * x + 2];
    }
    void setTo0(int l, int r){
        setTo0(l, r, 0, 0, sz);
    }
    int walk(int val, int x, int lx, int rx, int curr){
        if(rx - lx == 1){
            if(curr + sum[x] == val) return lx;
            else return -1;
        }
        int m = (lx + rx) / 2;
        push(x);
        if(sum[2 * x + 1] + curr >= val){
            return walk(val, 2 * x + 1, lx, m, curr);
        }else{
            return walk(val, 2 * x + 2, m, rx, curr + sum[2 * x + 1]);
        }
    }
    int walk(int val){
        return walk(val, 0, 0, sz, 0);
    }
};
 
struct segTreeMax{
    vector<int> mx;
    int sz;
    void init(int n){
        sz = 1;
        while(sz < n) sz *= 2;
        mx.assign(2 * sz, 0);
    }
    void set(int i, int val, int x, int lx, int rx){
        if(rx - lx == 1){
            mx[x] = val;
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m) set(i, val, 2 * x + 1, lx, m);
        else set(i, val, 2 * x + 2, m, rx);
        mx[x] = max(mx[2 * x + 1], mx[2 * x + 2]);
    }
    void set(int i, int val){
        set(i, val, 0, 0, sz);
    }
    int calc(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r) return mx[x];
        else if(lx >= r || rx <= l) return 0;
        int m = (lx + rx) / 2;
        int c1 = calc(l, r, 2 * x + 1, lx, m);
        int c2 = calc(l, r, 2 * x + 2, m, rx);
        return max(c1, c2);
    }
    int calc(int l, int r){
        if(l >= r) return 0;
        return calc(l, r, 0, 0, sz);
    }
    int walk(int val, int x, int lx, int rx){
        if(rx - lx == 1){
            if(mx[x] > val) return lx;
            else return -1;
        }
        int m = (lx + rx) / 2;
        if(mx[2 * x + 1] > val){
            return walk(val, 2 * x + 1, lx, m);
        }else return walk(val, 2 * x + 2, m, rx);
    }
    int walk(int val){
        return walk(val, 0, 0, sz);
    }
};
 
struct segTreeSum{
    vector<int> sum;
    int sz;
    void init(int n){
        sz = 1;
        while(sz < n) sz *= 2;
        sum.assign(2 * sz, 0);
    }
    void set(int i, int val, int x, int lx, int rx){
        if(rx - lx == 1){
            sum[x] = val;
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m) set(i, val, 2 * x + 1, lx, m);
        else set(i, val, 2 * x + 2, m, rx);
        sum[x] = sum[2 * x + 1] + sum[2 * x + 2];
    }
    void set(int i, int val){
        set(i, val, 0, 0, sz);
    }
    int calc(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r) return sum[x];
        else if(lx >= r || rx <= l) return 0;
        int m = (lx + rx) / 2;
        int c1 = calc(l, r, 2 * x + 1, lx, m);
        int c2 = calc(l, r, 2 * x + 2, m, rx);
        return c1 + c2;
    }
    int calc(int l, int r){
        if(l >= r) return 0;
        return calc(l, r, 0, 0, sz);
    }
};
 
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    vector<pair<int, int>> queries(C);
    segTreeFindRange rng; rng.init(N);
    vector<vector<int>> starts(N), ends(N);
    for(int i = 0; i < C; i++){
        S[i]++; E[i]++;
        //It goes from the first with prefix sum = S 
        //to first with prefix sum = E.
        int l = rng.walk(S[i]);
        int r = rng.walk(E[i]+1);
        if(r == -1) r = N;
        r--;
        rng.setTo0(l+1, r+1); //I do r+1 because it's half-open.
        queries[i] = {l, r};
        starts[l].push_back(i);
        ends[r].push_back(i);
    }
    segTreeSum stSum; stSum.init(C);
    segTreeMax stMax; stMax.init(C);
    segTreeMax mxRng; mxRng.init(N-1);
    for(int i = 0; i < N-1; i++){
        mxRng.set(i, K[i]);
    }
    int mxWins = 0;
    int ans = 0;
    for(int i = 0; i < N; i++){
        //I assume that the knight is at position i.
        for(int queryInd : starts[i]){
            stSum.set(queryInd, 1);
            int l = queries[queryInd].first;
            int r = queries[queryInd].second;
            stMax.set(queryInd, mxRng.calc(l, r));
            //I don't do r+1 because I don't want to include r
            //as there's the knight in the middle.
        }
        //Now I get the first round I would lose.
        int ind = stMax.walk(R);
        if(ind == -1) ind = C;
        int wins = stSum.calc(0, ind);
        if(mxWins < wins){
            mxWins = wins;
            ans = i;
        }
        for(int queryInd : ends[i]){
            stSum.set(queryInd, 0);
            stMax.set(queryInd, 0);
        }
    }
    return ans;
}

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