이 제출은 이전 버전의 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 nxt[111111],idx[333333];
set<pii> eff;
void put_(int p,int num){
for(p+=ele-1,idx[p]=num,p>>=1;p;p>>=1) idx[p]=max(idx[2*p],idx[2*p+1]);
}
int max_(int s,int e){
int mx=0;
s+=ele-1; e+=ele-1;
while(s<e){
if(s%2==1) mx=max(mx,idx[s++]);
if(e%2==0) mx=max(mx,idx[e--]);
s/=2; e/=2;
}
if(s==e) mx=max(mx,idx[s]);
return mx;
}
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];
for(int i=0;i<C;i++) s[i]=S[i];
for(int i=0;i<C;i++) e[i]=E[i];
for(int i=0;i<n;i++) nxt[i]=i+1;
for(int i=0;i<n-1;i++) put_(i+1,k[i]);
for(int i=0;i<c;i++){
int del=e[i]-s[i]; e[i]=s[i];
for(int j=0;j<=del;j++) e[i]=nxt[e[i]];
nxt[s[i]]=e[i]; e[i]--;
}
/*
for(int i=0;i<c;i++) printf("%d %d\n",s[i],e[i]);
printf("\n");
*/
for(int i=0;i<c;i++){
if(r==max(r,max_(s[i]+1,e[i]))){
eff.insert({s[i],1});
eff.insert({e[i]+1,-1});
}
}
/*
set<pii>::iterator itt=eff.begin();
while(itt!=eff.end()) printf("%d %d\n",itt->ff,itt->ss),itt++;
printf("\n");
*/
int mx=0,res=0;
set<pii>::iterator it=eff.begin();
for(int i=0;i<n;i++){
while(it!=eff.end() && it->ff==i) res+=it->ss,it++;
mx=max(mx,res);
}
return mx;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |