이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
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;
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |