oj.uz

Submission #1035306

# Submission time Handle Problem Language Result Execution time Memory
1035306 2024-07-26T09:07:36 Z Warinchai Jousting tournament (IOI12_tournament) C++14
0 / 100
 75 ms 7224 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,x.first,x.second-1);
        if(R>=mx)add[x.first]++,add[x.second+1]--;
    }
    pair<int,int>ans;
    int cans=0;
    for(int i=1;i<=N;i++){
        cans+=add[i];
        ans=max(ans,{cans,-i});
    }
    return -ans.second-1;

}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 856 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 916 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 776 KB Output is correct
9 Incorrect 2 ms 604 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3540 KB Output is correct
2 Correct 72 ms 7196 KB Output is correct
3 Correct 33 ms 5680 KB Output is correct
4 Correct 59 ms 7224 KB Output is correct
5 Correct 57 ms 7112 KB Output is correct
6 Correct 75 ms 6332 KB Output is correct
7 Correct 62 ms 7132 KB Output is correct
8 Correct 63 ms 7116 KB Output is correct
9 Incorrect 29 ms 5588 KB Output isn't correct
10 Halted 0 ms 0 KB -