Submission #242262

#	Time	Username	Problem	Language	Result	Execution time	Memory
242262		dantoh000	Jousting tournament (IOI12_tournament)	C++14	100 / 100	174 ms	19964 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 id[SZ];
int p[SZ];
int sc[SZ];
int leftpos[SZ];
int fw[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-2);
    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);
    fill(p,p+SZ,-1);
    fill(leftpos,leftpos+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]){
            //printf("removing %d %d\n",it->first,it->second);
            int ID = it->second;
            if (ID == -1){
                if (leftpos[i] == -1) leftpos[i] = it->first;
            }
            else p[ID] = 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 = C-1; i >= 0; i--){
        //printf("%d %d\n",l[i],r[i]);
        int mx = root->query(l[i],r[i]-1);
        if (mx == 1){
            sc[i] = 0;
        }
        else{
            //printf("will win tourney %d <%d,%d>\n",i,l[i],r[i]);
            if (p[i] == -1) sc[i] = 1;
            else sc[i] = sc[p[i]] + 1;
        }
    }
    for (int i = 0; i < C; i++){
        //printf("parent of tourney %d is tourney %d, leftpos %d\n",i,p[i],leftpos[i]);
    }
    int bestsc = 0;
    int ans = N-1;
    for (int i = 0; i < C; i++){
        //printf("tourney %d has score %d, pos %d\n",i,sc[i],leftpos[i]);
        if (bestsc < sc[i]){
            bestsc = sc[i];
            ans = leftpos[i];
            //printf("tourney %d has score %d, pos %d\n",i,sc[i],leftpos[i]);
        }
        else if (bestsc == sc[i]){
            //printf("tourney %d has score %d, pos %d\n",i,sc[i],leftpos[i]);
            ans = min(ans,leftpos[i]);
        }
    }
  return ans;

}

Compilation message (stderr)

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

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