oj.uz

Submission #696788

# Submission time Handle Problem Language Result Execution time Memory
696788 2023-02-07T09:21:29 Z vjudge1 Jousting tournament (IOI12_tournament) C++17
100 / 100
 86 ms 20724 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7360 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7368 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 7 ms 8020 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 8 ms 7892 KB Output is correct
5 Correct 10 ms 7956 KB Output is correct
6 Correct 9 ms 7816 KB Output is correct
7 Correct 9 ms 8020 KB Output is correct
8 Correct 7 ms 7892 KB Output is correct
9 Correct 6 ms 7656 KB Output is correct
10 Correct 8 ms 7960 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11820 KB Output is correct
2 Correct 86 ms 20724 KB Output is correct
3 Correct 45 ms 12612 KB Output is correct
4 Correct 71 ms 19556 KB Output is correct
5 Correct 67 ms 19524 KB Output is correct
6 Correct 69 ms 16256 KB Output is correct
7 Correct 70 ms 19696 KB Output is correct
8 Correct 85 ms 19872 KB Output is correct
9 Correct 36 ms 12132 KB Output is correct
10 Correct 48 ms 12608 KB Output is correct