oj.uz

Submission #1035327

# Submission time Handle Problem Language Result Execution time Memory
1035327 2024-07-26T09:25:06 Z Warinchai Jousting tournament (IOI12_tournament) C++14
100 / 100
 686 ms 9784 KB 
#include<bits/stdc++.h>
using namespace std;
int n;
struct segpos{
    int info[400005];
    void use(int i){upd(1,n,1,i);}
    void upd(int st,int en,int i,int pos){
        if(st==en){
            info[i]=0;
            //cerr<<st<<" "<<en<<" "<<i<<":"<<info[i]<<"\n";
            return;
        }
        int m=(st+en)/2;
        if(pos<=m)upd(st,m,i*2,pos);
        else upd(m+1,en,i*2+1,pos);
        info[i]=info[i*2]+info[i*2+1];
        //cerr<<st<<" "<<en<<" "<<i<<":"<<info[i*2]<<"+"<<info[i*2+1]<<"\n";
    }
    int get(int st,int en,int i,int pos){
        //cerr<<st<<' '<<en<<":"<<info[i]<<"\n";
        if(st==en){
            //cerr<<"get:"<<st<<"\n";
            return st;
        }
        int m=(st+en)/2;
        if(pos<=info[i*2])return get(st,m,i*2,pos);
        else return get(m+1,en,i*2+1,pos-info[i*2]);
    }
    int get(int i){return get(1,n,1,i);}
    void build(int st,int en,int i){
        if(st==en)return void(info[i]=1);
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
}pst,pen;
int val[100005];
int add[100005];
struct segmax{
    int info[400005];
    void build(int st,int en,int i){
        if(st==en)return void(info[i]=val[st]);
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=max(info[i*2],info[i*2+1]);
    }
    int fmax(int st,int en,int i,int l,int r){
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return max(fmax(st,m,i*2,l,r),fmax(m+1,en,i*2+1,l,r));
    }
}tr;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    for(int i=0;i<N-1;i++){
        val[i+1]=K[i];
    }
    tr.build(1,N-1,1);
    vector<pair<int,int>>op;
    pst.build(1,n,1);
    pen.build(1,n,1);
    for(int i=0;i<C;i++){
        /*cerr<<"info:"<<"\n";
        for(int i=1;i<=n;i++)cerr<<pst.get(i)<<" ";
        cerr<<"\n";
        for(int i=1;i<=n;i++)cerr<<pen.get(i)<<" ";
        cerr<<"\n";*/
        S[i]++,E[i]++;
        int st=pst.get(S[i]);
        int en=pen.get(E[i]);
        cerr<<"range:"<<st<<" "<<en<<"\n";
        op.push_back({st,en});
        vector<int>upst,upen;
        for(int j=S[i];j<=E[i];j++){
            if(j!=S[i])upst.push_back(pst.get(j));
            if(j!=E[i])upen.push_back(pen.get(j));
        }
        for(auto x:upst)/*cerr<<"upd:"<<x<<"\n",*/pst.use(x);
        //cerr<<"\n";
        for(auto x:upen)/*cerr<<"upd:"<<x<<"\n",*/pen.use(x);
    }
    vector<pair<int,int>>rop;
    for(auto x:op){
        int mx=tr.fmax(1,n-1,1,x.first,x.second-1);
        if(R>=mx)add[x.first]++,add[x.second+1]--;
    }
    pair<int,int>ans={INT_MIN,INT_MIN};
    int cans=0;
    for(int i=1;i<=N;i++){
        cans+=add[i];
        cerr<<cans<<" ";
        ans=max(ans,{cans,-i});
    }
    cerr<<"\n";
    return -ans.second-1;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 456 KB Output is correct
7 Correct 4 ms 448 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 344 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 36 ms 908 KB Output is correct
3 Correct 13 ms 600 KB Output is correct
4 Correct 36 ms 860 KB Output is correct
5 Correct 37 ms 860 KB Output is correct
6 Correct 28 ms 860 KB Output is correct
7 Correct 35 ms 916 KB Output is correct
8 Correct 35 ms 860 KB Output is correct
9 Correct 11 ms 600 KB Output is correct
10 Correct 38 ms 876 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 4300 KB Output is correct
2 Correct 651 ms 9640 KB Output is correct
3 Correct 253 ms 5932 KB Output is correct
4 Correct 649 ms 9676 KB Output is correct
5 Correct 623 ms 9576 KB Output is correct
6 Correct 542 ms 8400 KB Output is correct
7 Correct 672 ms 9784 KB Output is correct
8 Correct 686 ms 9672 KB Output is correct
9 Correct 207 ms 5840 KB Output is correct
10 Correct 223 ms 5456 KB Output is correct