oj.uz

Submission #684900

# Submission time Handle Problem Language Result Execution time Memory
684900 2023-01-22T19:17:47 Z Khizri Jousting tournament (IOI12_tournament) C++17
100 / 100
 77 ms 20624 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;
}
/*
5 3 2
3 0 1 4
2 4
1 2
0 1
*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 4 ms 7360 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7364 KB Output is correct
7 Correct 6 ms 7364 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 6 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 7960 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 7 ms 7892 KB Output is correct
5 Correct 8 ms 7880 KB Output is correct
6 Correct 7 ms 7824 KB Output is correct
7 Correct 7 ms 8012 KB Output is correct
8 Correct 10 ms 7948 KB Output is correct
9 Correct 7 ms 7636 KB Output is correct
10 Correct 8 ms 7892 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11336 KB Output is correct
2 Correct 69 ms 20624 KB Output is correct
3 Correct 37 ms 12596 KB Output is correct
4 Correct 75 ms 19620 KB Output is correct
5 Correct 71 ms 19556 KB Output is correct
6 Correct 77 ms 16328 KB Output is correct
7 Correct 71 ms 19620 KB Output is correct
8 Correct 70 ms 19892 KB Output is correct
9 Correct 37 ms 12104 KB Output is correct
10 Correct 40 ms 12592 KB Output is correct