#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int TREE_SIZE=1<<17;
int max_tree[2*TREE_SIZE];
void set_max_tree(int i,int v){
int node=TREE_SIZE+i;
max_tree[node]=v;
node/=2;
while(node){
max_tree[node]=max(max_tree[2*node],max_tree[2*node+1]);
node/=2;
}
}
int get_max(int node,int l,int r,int rl,int rr){
if(r<=rl||rr<=l)
return 0;
if(l<=rl&&rr<=r)
return max_tree[node];
int mid=(rl+rr)/2;
return max(get_max(2*node,l,r,rl,mid),get_max(2*node+1,l,r,mid,rr));
}
int get_max(int l,int r){
return get_max(1,l,r,0,TREE_SIZE);
}
bool get_interval(int left,int right,int r){
//cout<<"call "<<left<<" "<<right<<" "<<r<<"\n";
right--;
int m=get_max(left,right);
//cout<<"return "<<(m<r)<<"\n";
return m<r;
}
int GetBestPosition(int n,int c,int r,int *K,int *L,int *R){
for(int i=0;i<c;i++)
R[i]++;
vector<int>present(n,1);
for(int j=0;j<c;j++){
int sum=0;
int l=n,r=n;
for(int i=0;i<n;i++){
if(sum==L[j]&&l==n)
l=i;
if(sum==R[j]&&r==n)
r=i;
sum+=present[i];
}
L[j]=l;
R[j]=r;
//cout<<l<<" "<<r<<"\n";
for(int i=l;i<r-1;i++)
present[i]=0;
}
for(int i=0;i<n-1;i++)
set_max_tree(i,K[i]);
int max_res=-1;
int i_res=0;
vector<pair<int,int>>ranges1(c),ranges2(c);
for(int i=0;i<c;i++){
ranges1[i]={L[i],R[i]};
ranges2[i]={R[i],L[i]};
}
sort(ranges1.begin(),ranges1.end());
sort(ranges2.begin(),ranges2.end());
int i1=0,i2=0;
int res=0;
for(int ins=0;ins<n;ins++){
//(int i:arr)
//cout<<i<<" ";
//cout<<"\n";
while(i1<c&&ranges1[i1].first==ins){
//cout<<"+ "<<ranges1[i1].first<<" "<<ranges1[i1].second<<" "<<r<<"\n";
res+=get_interval(ranges1[i1].first,ranges1[i1].second,r);
i1++;
}
while(i2<c&&ranges2[i2].first==ins){
//cout<<"- "<<ranges2[i2].second<<" "<<ranges2[i2].first<<" "<<r<<"\n";
res-=get_interval(ranges2[i2].second,ranges2[i2].first,r);
i2++;
}
//for(int j=0;j<c;j++){
//res+=get_interval(L[j],R[j],ins,r);
//}
//if(n<10)
//cout<<ins<<" "<<res<<"\n";
if(res>max_res){
max_res=res;
i_res=ins;
}
}
return i_res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
26 ms |
604 KB |
Output is correct |
3 |
Correct |
3 ms |
348 KB |
Output is correct |
4 |
Correct |
26 ms |
580 KB |
Output is correct |
5 |
Correct |
22 ms |
592 KB |
Output is correct |
6 |
Correct |
17 ms |
604 KB |
Output is correct |
7 |
Correct |
26 ms |
596 KB |
Output is correct |
8 |
Correct |
28 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
29 ms |
576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1014 ms |
856 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |