#include <bits/stdc++.h>
using namespace std;
const int N=100006;
struct node{
int cnt;
int maximum,noRight;
int height;
} sg[4*N];
node operator +(const node a,const node b){
node c;
c.cnt=a.cnt+b.cnt;
c.maximum=max(a.maximum,b.maximum);
c.noRight=max(a.maximum,b.noRight);
c.height=max(a.height,b.height);
return c;
}
void build (int v,int tl,int tr,int arr[]){
if (tl==tr){
sg[v].cnt=1;
sg[v].noRight=0;
sg[v].maximum=arr[tl];
sg[v].height=1;
return;
}
int tm=(tl+tr)/2;
build(v+v,tl,tm,arr);
build(v+v+1,tm+1,tr,arr);
sg[v]=sg[v+v]+sg[v+v+1];
}
void del(int v,int tl,int tr,int l,int r){
if (l>r) return;
if (l==1 && r==sg[v].cnt){
sg[v].cnt=0;
sg[v].maximum=sg[v].noRight=0;
sg[v].height=0;
return;
}
int border=sg[v+v].cnt,tm=(tl+tr)/2;
del(v+v,tl,tm,l,min(border,r));
del(v+v+1,tm+1,tr,max(border+1,l)-border,r-border);
sg[v]=sg[v+v]+sg[v+v+1];
}
void update (int v,int tl,int tr,int ind,node newNode){
if (sg[v].cnt==1){
sg[v].maximum=newNode.maximum;
sg[v].noRight=newNode.noRight;
sg[v].height=newNode.height;
return;
}
int border=sg[v+v].cnt,tm=(tl+tr)/2;
if (ind<=border)
update(v+v,tl,tm,ind,newNode);
else
update(v+v+1,tm+1,tr,ind-border,newNode);
sg[v]=sg[v+v]+sg[v+v+1];
}
node query(int v,int tl,int tr,int l,int r){
if (l>r) return {0,0,0,0};
//cout<<l<<" "<<r<<" "<<sg[v].cnt<<endl;
if (l==1 && r==sg[v].cnt){
return sg[v];
}
int border=sg[v+v].cnt,tm=(tl+tr)/2;
node left=query(v+v,tl,tm,l,min(border,r));
node right=query(v+v+1,tm+1,tr,max(border+1,l)-border,r-border);
return left+right;
}
int GetBestPosition(int n, int q, int addVal, int rank[], int start[], int end[]) {
pair<int,int> finalAns={1,0};
if (n==1) return 0;
build(1,0,n-2,rank);
for (int i=0;i<q;i++){
node ans=query(1,0,n-2,start[i]+1,end[i]+1);
del(1,0,n-2,start[i]+2,end[i]+1);
ans.height++;
finalAns=max(finalAns,{ans.height,start[i]+1});
update(1,0,n-2,start[i]+1,ans);
}
return finalAns.second;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
6276 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
