#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 mp[111111];
int idx[333333],qur[333333];
set<pii> st,eff;
void putm_(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]);
}
void putq_(int p,int num){
for(p+=ele-1;p;p>>=1) qur[p]+=num;
}
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;
}
void clear_(int p){
qur[p]=0;
if(p<ele){
if(qur[2*p]) clear_(2*p);
if(qur[2*p+1]) clear_(2*p+1);
}
}
int sum_(int s,int e){
int sum=0;
s+=ele-1; e+=ele-1;
while(s<e){
if(s%2==1){
if(qur[s]) sum+=qur[s],clear_(s);
s++;
}
if(e%2==0){
if(qur[e]) sum+=qur[e],clear_(e);
e--;
}
s/=2; e/=2;
}
if(s==e && qur[s]) sum+=qur[s],clear_(s);
return sum;
}
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-1;i++) putm_(i+1,k[i]);
for(int i=0;i<c;i++){
int ran,bef=e[i];
while(ran=sum_(s[i]+1,e[i]+1)){
set<pii>::iterator it=st.lower_bound({s[i]+1,0});
while(it!=st.end() && it->ff<=e[i]) putq_(it->ff,-it->ss),st.erase(it++);
e[i]+=ran;
}
putq_(s[i]+1,e[i]-s[i]);
st.insert({s[i]+1,e[i]-s[i]});
/*
for(int j=1;j<16;j++) printf("%d %d\n",j,qur[j]);
printf("\n");
*/
}
/*
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;
/*
for(int p=0;p<n;p++){
for(int i=0;i<n;i++){
if(i<p) mp[i]=k[i];
else if(i==p) mp[i]=r;
else mp[i]=k[i-1];
}
for(int i=0;i<n;i++) printf("%d ",mp[i]);
printf("\n");
}
printf("\n");
*/
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:74:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
while(ran=sum_(s[i]+1,e[i]+1)){
^
tournament.cpp:73:17: warning: unused variable 'bef' [-Wunused-variable]
int ran,bef=e[i];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5512 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
5512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
7624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
