Submission #242368

#	Time	Username	Problem	Language	Result	Execution time	Memory
242368		dantoh000	Jousting tournament (IOI12_tournament)	C++14	100 / 100	198 ms	17528 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
const int SZ = 100005;
typedef pair<int,int> ii;
int l[SZ], r[SZ], RR[SZ];
int fw[SZ];
int a[SZ];
void up(int x, int nv){
    x++;
    while (x < SZ){
        fw[x]+=nv;
        x += x&-x;
    }
}
int sum(int x){
    x++;
    int ret = 0;
    while (x){
        ret += fw[x];
        x -=x&-x;
    }
    return ret;
}
set<ii> pos;
struct node{
    int s,e,m,v;
    node *l, *r;
    node (int _s ,int _e): s(_s), e(_e){
        m = (s+e)/2;
        v = 0;
        if (s != e){
            l = new node(s,m);
            r= new node(m+1,e);
        }
    }
    void up(int x){
        if (s == e){
            v = 1; return;
        }
        if (x > m) r->up(x);
        else if (x <= m) l->up(x);
        v = l->v|r->v;
    }
    int query(int qs, int qe){
        if (qs == s && qe == e){ return v; }
        else{
            if (qs > m) return r->query(qs,qe);
            else if (qe <= m) return l->query(qs,qe);
            else return l->query(qs,m) | r->query(m+1,qe);
        }
    }

}*root;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    root = new node(0,N-1);
    for (int i = 0; i < N-1; i++) {
        if (K[i] > R) root->up(i);
    }
    fill(l,l+SZ,-1);
    fill(r,r+SZ,-1);
    iota(RR,RR+SZ,0);
    for (int i = 0; i < N; i++){
        up(i,1);
        pos.insert({i,-1});
    }
    for (int i = 0; i < C; i++){
        int cur = 0;
        int lo = 0, hi = N;
        while (lo < hi){
            int mid = (lo+hi)/2;
            if (sum(mid) < S[i]+1) lo = mid+1;
            else hi = mid;
        }
        l[i] = lo;
        lo = 0, hi = N;
        while (lo < hi){
            int mid = (lo+hi)/2;
            if (sum(mid) < E[i]+1) lo = mid+1;
            else hi = mid;
        }
        r[i] = RR[lo];
        //printf("tourney %d covers <%d,%d>\n",i,l[i],r[i]);
        if (l[i] == N) return 1;
        auto it = pos.lower_bound({l[i],-1});
        while (it != pos.end() && it->first <= r[i]){
            up(it->first,-1);
            it = pos.erase(it);
        }
        RR[l[i]] = r[i];
        pos.insert({l[i],i});
        up(l[i],1);
    }
    for (int i = 0; i < C; i++){
        if (!root->query(l[i],r[i]-1)){
            //printf("updating %d %d\n",l[i],r[i]);
            a[l[i]]++;
            a[r[i]+1]--;
        }
    }
    int ans = 0;
    for (int i = 1; i < N; i++){
        a[i] += a[i-1];
        if (a[i] > a[ans]) {
            //printf("%d %d\n",i,a[i]);
            ans = i;
        }
    }
    return ans;

}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:67:13: warning: unused variable 'cur' [-Wunused-variable]
         int cur = 0;
             ^~~

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