이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
int N,C,R,K[100001],S[100001],E[100001];
int arr[100005];
vector<int>adj[200005];
int ID;
int tree[200005];
int l[200005],r[200005],store[200005];
int dis[200005];
int strong[200005];
void dfs(int node){
if (node<=N){
l[node]=node;
r[node]=node;
if (strong[r[node]-1]-strong[l[node]-1]==0)
store[node]=l[node];
else
store[node]=INF;
dis[node]=0;
return;
}
l[node]=INF;
r[node]=-INF;
store[node]=INF;
dis[node]=-INF;
for (int x:adj[node]){
dfs(x);
l[node]=min(l[node],l[x]);
r[node]=max(r[node],r[x]);
if (store[x]==INF) continue;
if (dis[x]+1>dis[node]){
dis[node]=dis[x]+1;
store[node]=store[x];
}
else if (dis[x]+1==dis[node])
store[node]=min(store[node],store[x]);
}
}
int query(int pos){
int ans=0;
while (pos>=1){
ans+=tree[pos];
pos-=(pos&(-pos));
}
return ans;
}
void update(int pos, int val){
while (pos<=N){
tree[pos]+=val;
pos+=(pos&(-pos));
}
}
int getKth(int k){
int low=0,high=N+1,mid;
while (low+1<high){
mid=(low+high)/2;
//cout<<mid<<' '<<query(mid)<<endl;
if (query(mid)>=k)
high=mid;
else
low=mid;
}
return high;
}
int GetBestPosition(int NN, int CC, int RR, int K[], int S[], int E[]){
N=NN; C=CC; R=RR;
for (int i=N-1;i>=1;i--){
K[i]=K[i-1];
if (K[i]>R)
strong[i]++;
}
for (int i=1;i<=N;i++)
strong[i]+=strong[i-1];
for (int i=1;i<=N;i++){
arr[i]=i;
update(i,1);
}
ID=N;
for (int i=0;i<C;i++){
int len=E[i]-S[i]+1;
S[i]++; E[i]++;
ID++;
int repl;
for (int j=0;j<len;j++){
int ind=getKth(S[i]);
repl=ind;
adj[ID].push_back(arr[ind]);
arr[ind]=0;
update(ind,-1);
}
arr[repl]=ID;
update(repl,1);
}
dfs(ID);
int ans=0,realAns=INF;
for (int i=ID;i>N;i--){
if (store[i]!=INF && strong[r[i]-1]-strong[l[i]-1]==0){
if (dis[i]>ans){
ans=max(ans,dis[i]);
realAns=store[i];
}
else if (dis[i]==ans)
realAns=min(realAns,store[i]);
}
}
return realAns-1;
}
컴파일 시 표준 에러 (stderr) 메시지
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:60:8: warning: 'repl' may be used uninitialized in this function [-Wmaybe-uninitialized]
pos+=(pos&(-pos));
~~~^~~~~~~~~~~~~~
tournament.cpp:95:9: note: 'repl' was declared here
int repl;
^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |