Submission #388919

#	Time	Username	Problem	Language	Result	Execution time	Memory
388919		faresbasbs	Jousting tournament (IOI12_tournament)	C++14	100 / 100	82 ms	7060 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
int n,c,rnk,t,pref[1000001],rt[1000001];
vector<pair<int,int>> segment2;
vector<int> segment;

int getpos(int val){
    int curr = 1 , tot = 0;
    while(curr < t){
        if(segment[2*curr]+tot >= val){
            curr = 2*curr;
        }else{
            tot += segment[2*curr];
            curr = 2*curr+1;
        }
    }
    return curr-t+1;
}

void del(int curr){
    while(curr){
        segment[curr] -= 1;
        curr /= 2;
    }
}

void upd(pair<int,int> val , int pos){
    if(val.first > segment2[pos].first || (val.first == segment2[pos].first && val.second < segment2[pos].second)){
        segment2[pos] = val;
    }
    pos /= 2;
    while(pos){
        if(segment2[2*pos].first > segment2[2*pos+1].first || (segment2[2*pos].first == segment2[2*pos+1].first && segment2[2*pos].second < segment2[2*pos+1].second)){
            segment2[pos] = segment2[2*pos];
        }else{
            segment2[pos] = segment2[2*pos+1];
        }
        pos /= 2;
    }
}

pair<int,int> getmax(int a , int b , int curr , int l , int r){
    if(b < l || a > r){
        return {0,0};
    }
    if(a <= l && b >= r){
        return segment2[curr];
    }
    int mid = (l+r)/2;
    pair<int,int> lv = getmax(a,b,2*curr,l,mid) , rv = getmax(a,b,2*curr+1,mid+1,r);
    if(lv.first > rv.first || (lv.first == rv.first && lv.second < rv.second)){
        return lv;
    }
    return rv;
}

int GetBestPosition(int N , int C , int R , int *K , int *S , int *E){
    n = N , c = C , rnk = R;
    t = pow(2,ceil(log2(n)));
    segment.resize(2*t,0);
    segment2.resize(2*t,{0,0});
    for(int i = 1 ; i < n ; i += 1){
        pref[i] = pref[i-1]+(K[i-1] > R ? 1 : 0);
    }
    for(int i = t ; i < t+n ; i += 1){
        rt[i-t+1] = i-t+1;
        segment[i] = 1;
    }
    for(int i = t-1 ; i > 0 ; i -= 1){
        segment[i] = segment[2*i]+segment[2*i+1];
    }
    int ans = 0 , pos = 1;
    for(int i = 0 ; i < c ; i += 1){
        int l = S[i]+1 , r = E[i]+1 , maxi = 0;
        while(r > l){
            int f = getpos(l+1);
            del(f+t-1);
            maxi = max(maxi,rt[f]);
            r -= 1;
        }
        int f = getpos(l);
        rt[f] = max(rt[f],maxi);
        l = f , r = rt[f];
        if(pref[r-1]-pref[l-1] > 0){
            continue;
        }
        pair<int,int> g = getmax(l,r,1,1,t);
        g.first += 1;
        if(g.first == 1){
            g.second = l;
        }
        if(g.first > ans || (g.first == ans && g.second < pos)){
            ans = g.first;
            pos = g.second;
        }
        upd(g,l+t-1);
    }
    return pos-1;
}

/*int main(){
    vector<int> K = {1,0,2,4} , S = {1,0,0} , E = {3,1,1};
    cout << GetBestPosition(5,3,3,K,S,E) << endl;
}*/

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