#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],res[111111];
void put_(int p,int num){
for(p+=ele,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; e+=ele;
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,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],e[i]-1))){
res[s[i]]++;
res[e[i]+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,sum=0;
for(int i=0;i<n;i++){
sum+=res[i];
mx=max(mx,sum);
}
return mx;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
4584 KB |
Output is correct |
2 |
Incorrect |
0 ms |
4584 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
4584 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
5032 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |