Submission #242218

#	Time	Username	Problem	Language	Result	Execution time	Memory
242218		dwsc	Jousting tournament (IOI12_tournament)	C++14	100 / 100	131 ms	13560 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
int ft[100010];
int pos[100010];
int jump[100010];
int n;
void up(int x,int v){
    while (x <= n){
        ft[x] += v;
        x += (x&-x);
    }
}
int rsq(int b){
    int sum = 0;
    while (b){
        sum += ft[b];
        b -= b&-b;
    }
    return sum;
}
void uppos(int x,int v){
    while (x <= n){
        pos[x] += v;
        x += (x&-x);
    }
}
int rsqpos(int b){
    int sum = 0;
    while (b){
        sum += pos[b];
        b -= b&-b;
    }
    return sum;
}
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,int v1){
        if (s == e) {v = v1;return;}
        if (x <= m) l->up(x,v1);
        else r->up(x,v1);
        v = max(l->v,r->v);
    }
    int rmq(int x,int y){
        if (s == x && e == y) return v;
        if (y <= m) return l->rmq(x,y);
        if (x > m) return r->rmq(x,y);
        return max(l->rmq(x,m),r->rmq(m+1,y));
    }
}*root;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N;
    for (int i = 1; i <= n; i++) uppos(i,1);
    for (int i = 1; i <= n; i++) jump[i] = i+1;
    root = new node(1,n-1);
    for (int i = 0; i < n-1; i++) root->up(i+1,K[i]);
    for (int i = 0; i < C; i++){
        //for (int j = 1; j <= n; j++) cout << rsqpos(j) << " ";
        //cout << "hi\n";
        int s = S[i]+1,e = E[i]+1;
        int lo1 = 0,hi1 = n+1;
        int leftpos = -1;
        while (lo1 != hi1){
            //cout << lo1 << " " << hi1 << "\n";
            int m = (lo1+hi1)/2;
            int position = rsqpos(m);
            if (position >= s){
                leftpos = m;
                hi1 = m;
            }
            else{
                lo1 = m+1;
            }
        }
        int lo2 = 0,hi2 = n+1;
        int rightpos = -1;
        while (lo2 != hi2){
            //cout << lo2 << " " << hi2 << "\n";
            int m = (lo2+hi2)/2;
            int position = rsqpos(m);
            if (position <= e){
                rightpos = m;
                lo2 = m+1;
            }
            else{
                hi2 = m;
            }
        }
        //cout << leftpos << " " << rightpos << "\n";
        int score = root->rmq(leftpos,rightpos-1);
        if (score < R){
            up(leftpos,1);
            up(rightpos+1,-1);
        }
        int start = leftpos;
        while (jump[start] != rightpos+1){
            uppos(jump[start],-1);
            start = jump[start];
        }
        jump[leftpos] = rightpos+1;
        //for (int j = 1; j <= n; j++) cout << rsqpos(j) << " ";
        //cout << "\n";
    }
    int ans = -1,maxi = -1;
    for (int i = 1; i <= n; i++){
        if (rsq(i) > maxi){
            maxi = rsq(i);
            ans = i;
        }
    }
    return ans-1;
}

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