Submission #430510

#	Time	Username	Problem	Language	Result	Execution time	Memory
430510		MarcoMeijer	Jousting tournament (IOI12_tournament)	C++14	100 / 100	171 ms	23432 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }

const int MX = 2e5;
const int N = (1<<20);

struct Seg {
    int cnt[N*2], laz[N*2];
    void build(int p=1, int l=0, int r=N-1) {
        if(l == r) {
            cnt[p] = 1;
            return;
        }
        laz[p] = 0;
        int m=(l+r)/2;
        build(p*2,l,m);
        build(p*2+1,m+1,r);
        cnt[p] = cnt[p*2]+cnt[p*2+1];
    }
    void push(int p) {
        if(!laz[p]) return;
        cnt[p*2] = cnt[p*2+1] = 0;
        laz[p*2] = laz[p*2+1] = 1;
        laz[p] = 0;
    }
    void removeSeg(int i, int j, int p=1, int l=0, int r=N-1) {
        if(j < l || i > r) return;
        if(i <= l && j >= r) {
            laz[p] = 1;
            cnt[p] = 0;
            return;
        }
        push(p);
        int m=(l+r)/2;
        removeSeg(i,j,p*2,l,m);
        removeSeg(i,j,p*2+1,m+1,r);
        cnt[p] = cnt[p*2]+cnt[p*2+1];
    }
    int getSeg(int i, int j, int p=1, int l=0, int r=N-1) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return cnt[p];
        push(p);
        int m=(l+r)/2;
        int a=getSeg(i,j,p*2,l,m);
        int b=getSeg(i,j,p*2+1,m+1,r);
        return a+b;
    }
    int getFirst(int x, int p=1, int l=0, int r=N-1) {
        if(l == r) return l;
        push(p);

        int m=(l+r)/2;
        if(cnt[p*2] >= x) return getFirst(x,p*2,l,m);
        else return getFirst(x-cnt[p*2],p*2+1,m+1,r);
    }
} segCnt;

struct SegMax {
    int seg[N*2];
    void set(int i, int v, int p=1, int l=0, int r=N-1) {
        if(i < l || i > r) return;
        if(l == r) {
            seg[p] = v;
            return;
        }
        int m=(l+r)/2;
        set(i,v,p*2  ,l  ,m);
        set(i,v,p*2+1,m+1,r);
        seg[p] = max(seg[p*2], seg[p*2+1]);
    }
    int get(int i, int j, int p=1,int l=0, int r=N-1) {
        if(j < l || i > r) return -1;
        if(i <= l && j >= r) return seg[p];
        int m=(l+r)/2;
        int a=get(i,j,p*2  ,l  ,m);
        int b=get(i,j,p*2+1,m+1,r);
        return max(a,b);
    }
} segMax;


int GetBestPosition(int n, int c, int r, int *K, int *S, int *E) {
    segCnt.build();
    RE(i,c) {
        int a = segCnt.getFirst(S[i]+1);
        int b = segCnt.getFirst(E[i]+2)-1;
        segCnt.removeSeg(a+1,b);
        S[i] = a;
        E[i] = b;
    }
    vector<vi> beg, ed;
    beg.assign(n,vi()); ed.assign(n,vi());
    RE(i,c) beg[S[i]].pb(i);
    RE(i,c) ed[E[i]].pb(i);

    RE(i,n-1) segMax.set(i,K[i]);

    int ans = 0, maxCnt = 0;
    int cnt = 0;
    RE(i,n) {
        // place r at i
        FOR(j,beg[i])
            if(segMax.get(S[j],E[j]-1) < r)
                cnt++;
        if(cnt > maxCnt) {
            ans = i;
            maxCnt = cnt;
        }
        FOR(j,ed[i])
            if(segMax.get(S[j],E[j]-1) < r)
                cnt--;
    }

    return ans;
}

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