Submission #696788

#	Time	Username	Problem	Language	Result	Execution time	Memory
696788		vjudge1	Jousting tournament (IOI12_tournament)	C++17	100 / 100	86 ms	20724 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=3e5+5;
int n,q,k,sum[mxn],ans,id=1;
vector<int>arr;
vector<pii>idx,p2;
vector<int>vt[mxn];
int tree[4*mxn],p[mxn],f[mxn],dep[mxn],pl[mxn],pr[mxn],dix[mxn];
void build(int node,int l,int r){
    if(l==r){
        tree[node]=1;
        return;
    }
    int m=(l+r)/2;
    build(2*node,l,m);
    build(2*node+1,m+1,r);
    tree[node]=tree[2*node]+tree[2*node+1];
}
void update(int node,int l,int r,int idx){
    if(r<idx||idx<l) return;
    if(l==r){
        tree[node]=0;
        return;
    }
    int m=(l+r)/2;
    update(2*node,l,m,idx);
    update(2*node+1,m+1,r,idx);
    tree[node]=tree[2*node]+tree[2*node+1];
}
int findk(int node,int l,int r,int k){
    if(l==r){
        return l;
    }
    int m=(l+r)/2;
    if(tree[2*node]>=k){
        return findk(2*node,l,m,k);
    }
    else{
        return findk(2*node+1,m+1,r,k-tree[2*node]);
    }
}
void dfs(int u){
    int l=pl[u],r=pr[u];
    int x=l,y=r-1;
    if(y<x){
        return;
    }
    if(sum[y]-sum[x-1]!=0){
        for(int v:vt[u]){
            dfs(v);
        }
        return;
    }
    if(dep[u]<ans) return;
    if(ans<dep[u]){
        //cout<<u<<endl;
        ans=dep[u];
        id=dix[u];
    }
    else{
        //cout<<u<<endl;
        id=min(id,dix[u]);
    }
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    q=C;
    k=R;
    for(int i=0;i<n-1;i++){
        arr.pb(K[i]);
    }
    for(int i=0;i<q;i++){
        idx.pb({S[i],E[i]});
    }
    build(1,1,n);
    for(int i=1;i<=n;i++){
        p[i]=i;
        pl[i]=i;
        pr[i]=i;
        dix[i]=i;
    }
    int num=n;
    for(auto [l,r]:idx){
        l++,r++;
        int a=findk(1,1,n,l);
        ++num;
        pl[num]=1e9;
        pr[num]=-1e9;
        for(int i=r;i>=l+1;i--){
            int x=findk(1,1,n,i);
            vt[num].pb(p[x]);
            if(dep[p[x]]+1>dep[num]){
                dep[num]=dep[p[x]]+1;
                dix[num]=dix[p[x]];
            }
            else if(dep[num]==dep[p[x]]+1){
                dix[num]=min(dix[num],dix[p[x]]);
            }
            pl[num]=min(pl[num],pl[p[x]]);
            pr[num]=max(pr[num],pr[p[x]]);
            update(1,1,n,x);
        }
        if(dep[p[a]]+1>dep[num]){
            dep[num]=dep[p[a]]+1;
            dix[num]=dix[p[a]];
        }
        else if(dep[num]==dep[p[a]]+1){
            dix[num]=min(dix[num],dix[p[a]]);
        }
        pl[num]=min(pl[num],pl[p[a]]);
        pr[num]=max(pr[num],pr[p[a]]);
        vt[num].pb(p[a]);
        p[a]=num;
    }
    if(arr[0]>k){
        sum[1]=1;
    }
    else{
        sum[1]=0;
    }
    for(int i=2;i<n;i++){
        if(arr[i-1]>k){
            sum[i]=sum[i-1]+1;
        }
        else{
            sum[i]=sum[i-1];
        }
    }
    dfs(num);
    return id-1;
}

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