oj.uz

답안 #1035312

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035312 2024-07-26T09:13:21 Z Warinchai 마상시합 토너먼트 (IOI12_tournament) C++14
0 / 100
 68 ms 6160 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 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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Incorrect 1 ms 604 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2976 KB Output is correct
2 Correct 59 ms 6092 KB Output is correct
3 Correct 32 ms 5172 KB Output is correct
4 Correct 59 ms 6092 KB Output is correct
5 Correct 58 ms 5992 KB Output is correct
6 Correct 68 ms 5572 KB Output is correct
7 Correct 56 ms 6100 KB Output is correct
8 Correct 60 ms 6160 KB Output is correct
9 Incorrect 27 ms 5844 KB Output isn't correct
10 Halted 0 ms 0 KB -