Submission #205848

#	Time	Username	Problem	Language	Result	Execution time	Memory
205848		anonymous	Jousting tournament (IOI12_tournament)	C++14	100 / 100	188 ms	26988 KiB

tournament

#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
#define MAXN 100005
using namespace std;
class PersistentSegtree {
    int ST[MAXN * 30][3], R[MAXN], X[MAXN]={-1<<30}, V=1, P=1;
    int put(int ind, int l, int r, int cur) {
        if (l > ind || ind > r) {return(cur);}
        if (l == r) {
            ST[V][0] = ST[cur][0] + 1, V++;
            return(V-1);
        } else {
            int mid = (l+r) >> 1, p = V;
            V++;
            ST[p][1] = put(ind, l, mid, ST[cur][1]);
            ST[p][2] = put(ind, mid+1, r, ST[cur][2]);
            ST[p][0] = ST[ST[p][1]][0] + ST[ST[p][2]][0];
            return(p);
        }
    }
    int ask(int lo, int hi, int l, int r, int cur) {
        if (hi < l || lo > r || cur == 0) {return(0);}
        if (lo <= l && hi >= r) {return(ST[cur][0]);}
        else {
            int mid = (l+r) >> 1;
            return(ask(lo, hi, l, mid, ST[cur][1])+
                   ask(lo, hi, mid+1, r, ST[cur][2]));
        }
    }
public:
    void add(int x, int y) {
        R[P] = put(y, 0, MAXN, R[P-1]);
        X[P] = x, P++;
    }
    int Find(int x) { //largest index of largest not greater
        int lo = 0, hi = P;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (X[mid] > x) {hi = mid;}
            else {lo = mid;}
        }
        return(lo);
    }
    int sum(int xlo, int ylo, int xhi, int yhi) {
        int q1 = Find(xlo - 1), q2 = Find(xhi);
        return(ask(ylo, yhi, 0, MAXN, R[q2]) - ask(ylo, yhi, 0, MAXN, R[q1]));
    }
} PST;

class UFsegtree {
    int ST[MAXN*4];
public:
    void build(int l, int r, int cur) {
        if (l == r) {ST[cur]=1;}
        else {
            int mid = (l + r) >> 1;
            build(l, mid, 2*cur);
            build(mid+1, r, 2*cur+1);
            ST[cur] = r - l + 1;
        }
    }
    void upd(int ind, int l, int r, int cur) {
        if (ind < l || ind > r) {return;}
        if (l == r) {ST[cur]=0;}
        else {
            int mid = (l + r) >> 1;
            upd(ind, l, mid, 2*cur);
            upd(ind, mid+1, r, 2*cur+1);
            ST[cur] = ST[2*cur] + ST[2*cur + 1];
        }
    }
    int kth(int k, int l, int r, int cur) { //zero indexed
        if (l == r) {return(l);}
        int mid = (l + r) >> 1;
        if (k >= ST[2*cur]) {return(kth(k - ST[2*cur], mid+1, r, 2*cur+1));}
        else {return(kth(k, l, mid, 2*cur));}
    }
} ST;

int Range[MAXN][2], K[MAXN];
int pt1, pt2, best, bestpos;
vector <pair<int,int> > Seg;
int GetBestPosition(int N, int C, int R, int *K2, int *S, int *E) {
    ST.build(0, N-1, 1);
    for (int i=0; i<N; i++) {
        if (i != N-1) {K[i]=K2[i];}
        Range[i][0]=Range[i][1]=i;
    }
    for (int i=0; i<C; i++) {
        int li = ST.kth(S[i], 0, N-1, 1), ri = ST.kth(E[i], 0, N-1, 1);
        Seg.push_back({Range[li][0], Range[ri][1]});
        Range[li][1]=Range[ri][1];
        for (int j=S[i]+1; j<=E[i]; j++) {
            ST.upd(ST.kth(S[i]+1, 0, N-1, 1), 0, N-1,1);
        }
    }
    sort(Seg.begin(), Seg.end());
    for (auto s: Seg) {
        PST.add(s.first, s.second);
    }
    K[N-1] = R;
    pt2 = N-1; //rightmost good
    pt1 = N-1; //leftmost good
    for (int i=N-1; i>=0; i--) {
        while (pt1 && K[pt1-1] < R) {pt1--;}
        while (pt2 && K[pt2] > R) {pt2--;}
        int Score = PST.sum(pt1, 0, MAXN, pt2) - PST.sum(pt1, 0, MAXN, i-1) - PST.sum(i+1, 0, MAXN, pt2);
        if (best <= Score) {
            best = Score;
            bestpos=i;
        }
        if (!i) {break;}
        swap(K[i], K[i-1]);
        pt1=min(pt1, i-1);
        if (K[i] > K[i-1]) {pt2 = i-1;}
    }
    return(bestpos);
}

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