oj.uz

답안 #38887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38887 2018-01-07T14:47:11 Z andy627 마상시합 토너먼트 (IOI12_tournament) C++14
0 / 100
 29 ms 7640 KB 
#include <stdio.h>
#include <set>
#include <algorithm>
#define ff first
#define ss second
#define pii pair<int,int>
#define ele 131072
using namespace std;

int n,c,r;
int k[111111],s[111111],e[111111];
int ed[111111],res[111111];
int max_idx[333333],era[333333],sum_idx[333333];
set<pii> st;

void putm_(int p,int num){
    p+=ele; max_idx[p]=num;
    for(p>>=1;p;p>>=1) max_idx[p]=max(max_idx[2*p],max_idx[2*p+1]);
}

void puts_(int p,int num){
    for(p+=ele-1;p;p>>=1) sum_idx[p]+=num;
}

int max_(int s,int e){
    int mx=0;
    s+=ele; e+=ele;
    while(s<e){
        if(s%2==1) mx=max(mx,max_idx[s++]);
        if(e%2==0) mx=max(mx,max_idx[e--]);
        s/=2; e/=2;
    }
    if(s==e) mx=max(mx,max_idx[s]);

    return mx;
}

int get_real_pos(int n,int l,int r,int p){
    int m=(l+r)/2;

    if(l==r) return m;
    if(p<=sum_idx[2*n]) return get_real_pos(2*n,l,m,p);
    return get_real_pos(2*n+1,m+1,r,p-sum_idx[2*n]);
}

void erase_(int n,int l,int r,int s,int e){
    if(r<s || l>e) return;
    if(s<=l && r<=e){
        era[n]=1;
        sum_idx[n]=0;
        return;
    }

    int m=(l+r)/2;
    erase_(2*n,l,m,s,e);
    erase_(2*n+1,m+1,r,s,e);

    if(era[n]) sum_idx[n]=0;
    else sum_idx[n]=sum_idx[2*n]+sum_idx[2*n+1];
}

int GetBestPosition(int N,int C,int R,int *K,int *S,int *E){
    n=N; c=C; r=R;
    for(int i=0;i<N-1;i++) k[i]=K[i]+1;
    for(int i=0;i<C;i++) s[i]=S[i]+1;
    for(int i=0;i<C;i++) e[i]=E[i]+1;

    for(int i=1;i<=n;i++) puts_(i,1);
    for(int i=1;i<=n;i++) ed[i]=i;

    for(int i=0;i<c;i++){
        int ss=get_real_pos(1,1,ele,s[i]);
        int ee=get_real_pos(1,1,ele,e[i]); ee=ed[ee];
        s[i]=ss; e[i]=ee;
        erase_(1,1,ele,ss+1,ee);
        ed[ss]=ee;
    }

    for(int i=0;i<c;i++){
        if(r>max_(s[i],e[i]-1)){
            res[s[i]]++;
            res[e[i]+1]--;
        }
    }

    int mx=0,mxpos,tmp=0;
    for(int i=1;i<=n;i++){
        tmp+=res[i];
        if(mx<tmp){
            mx=tmp;
            mxpos=i;
        }
    }

    return mxpos-1;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:95:18: warning: 'mxpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return mxpos-1;
                  ^

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 7192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7192 KB Output is correct
2 Correct 6 ms 7192 KB Output is correct
3 Incorrect 0 ms 7192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 7640 KB Output isn't correct
2 Halted 0 ms 0 KB -