#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
#define mp make_pair
typedef long long llo;
#include"holiday.h"
llo it[100001];
llo n;
llo d;
llo ans=0;
llo ii;
llo tree[100000*4][2];
llo ind[100001];
llo co[2];
llo cur[2];
vector<llo> rr3;
vector<llo> rr2;
void update(llo no,llo l,llo r,llo i,llo val,llo tt){
tree[no][tt]+=val;
if(l==r){
}
else{
llo mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i,val,tt);
}
else{
update(no*2+2,mid+1,r,i,val,tt);
}
tree[no][tt]=tree[no*2+1][tt]+tree[no*2+2][tt];
}
}
llo xy=0;
llo query(llo no,llo l,llo r,llo k){
if(l==r){
return l;
}
else{
llo mid=(l+r)/2;
if(tree[no*2+1][0]<k){
return query(no*2+2,mid+1,r,k-tree[no*2+1][0]);
}
else{
return query(no*2+1,l,mid,k);
}
}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree[no][1];
}
else{
llo mid=(l+r)/2;
return query2(no*2+1,l,mid,aa,bb)+query2(no*2+2,mid+1,r,aa,bb);
}
}
void remove(int j){
update(0,0,n-1,ind[j],-1,0);
update(0,0,n-1,ind[j],-it[j],1);
}
void add(int j){
update(0,0,n-1,ind[j],1,0);
update(0,0,n-1,ind[j],it[j],1);
}
void solve(llo l,llo r,llo aa,llo bb,llo par=-1){
llo mid=(l+r)/2;
if(par==-1){
for(int i=mid;i<=r;i++){
add(i);
}
}
pair<llo,llo> cur={0,aa};
if(par!=-1){
if(par<mid){
for(int i=par;i<mid;i++){
remove(i);
}
}
else{
for(int i=mid;i<par;i++){
add(i);
}
for(int i=bb;i>aa;i--){
remove(i);
}
}
}
remove(aa);
for(llo x=aa;x<=bb;x++){
add(x);
llo le=d-2*(ii-mid)-(x-ii);
//mid to x range
if(le>0){
llo zz;
/* if(mid==1 and x==4){
xy=1;
cout<<le<<")"<<endl;
}*/
/* vector<llo> xx2;
for(llo k=mid;k<=x;k++){
xx2.pb(it[k]);
}
sort(xx2.begin(),xx2.end());
*/
llo su=0;
/* for(llo i=0;i<xx2.size();i++){
if(i+1>le){
break;
}
su+=xx2[i];
}*/
if(le<x-mid+1){
zz=query(0,0,n-1,le);
}
else{
zz=n-1;
}
// xy=0;
su=query2(0,0,n-1,0,zz);
/* if(mid==1 and x==4){
cout<<le<<")"<<zz<<"<"<<su<<endl;
}*/
if(su<cur.a){
cur={su,x};
}
}
}
for(int j=cur.b+1;j<=bb;j++){
remove(j);
}
// cout<<mid<<":"<<cur.a<<":"<<cur.b<<endl;
ans=min(ans,cur.a);
if(mid>l){
solve(l,mid-1,aa,cur.b,mid);
}
if(mid<r){
solve(mid+1,r,cur.b,bb,mid);
}
if(par!=-1){
if(par<mid){
for(int i=par;i<mid;i++){
add(i);
}
}
else{
for(int i=mid;i<par;i++){
remove(i);
}
for(int i=bb;i>aa;i--){
add(i);
}
}
}
for(int j=cur.b;j>aa;j--){
remove(j);
}
}
void solve(llo i){
multiset<llo> ss;
ii=i;
llo su=0;
for(llo j=i;j>=0;j--){
if(i-j>d){
break;
}
ss.insert(it[j]);
su+=it[j];
while(ss.size()>d-(i-j) and ss.size()>0){
auto j=ss.end();
j--;
su-=(*j);
ss.erase(j);
}
ans=min(ans,su);
}
if(i==0 or i==n-1){
return;
}
/* for(llo j=0;j<n;j++){
cout<<it[j]<<" ";
}
cout<<endl;
cout<<i<<".."<<endl;*/
vector<pair<llo,llo>> val;
for(llo j=0;j<n;j++){
val.pb({it[j],j});
}
sort(val.begin(),val.end());
for(llo k=0;k<2;k++){
for(llo j=0;j<4*n;j++){
tree[j][k]=0;
}
}
/* rr3.clear();
rr2.clear();
rr3.pb(0);
cur[0]=0;
cur[1]=0;*/
for(llo j=0;j<n;j++){
ind[val[j].b]=j;
}
/* for(llo j=0;j<n;j++){
cur[0]=update(cur[0],0,n-1,ind[j],1,0);
rr3.pb(cur[0]);
}
rr2.pb(0);
for(llo j=0;j<n;j++){
cur[1]=update(cur[1],0,n-1,val[j].b,val[j].a,1);
rr2.pb(cur[1]);
// cout<<val[j].a<<"...."<<val[j].b<<endl;
}
*/
//return ;
llo l=i;
while(l>0){
if((i-(l-1))*2<=d){
l--;
}
else{
break;
}
}
if(i==0 or i==n-1){
return;
}
// return ;
solve(l,i,i,n-1);
}
llo findMaxAttraction(int nn, int start, int dd, int at[]) {
n=nn;
d=dd;
ans=0;
for(llo i=0;i<n;i++){
it[i]=-at[i];
}
solve(start);
for(llo i=0;i<n/2;i++){
swap(it[i],it[n-i-1]);
}
solve(n-start-1);
return -ans;
}
Compilation message
holiday.cpp: In function 'void solve(llo)':
holiday.cpp:195:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
195 | while(ss.size()>d-(i-j) and ss.size()>0){
| ~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
6380 KB |
Output is correct |
| 2 |
Correct |
32 ms |
6380 KB |
Output is correct |
| 3 |
Correct |
31 ms |
6380 KB |
Output is correct |
| 4 |
Correct |
32 ms |
6380 KB |
Output is correct |
| 5 |
Correct |
36 ms |
4716 KB |
Output is correct |
| 6 |
Correct |
11 ms |
2028 KB |
Output is correct |
| 7 |
Correct |
20 ms |
3180 KB |
Output is correct |
| 8 |
Correct |
24 ms |
3180 KB |
Output is correct |
| 9 |
Correct |
8 ms |
1516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
35 ms |
844 KB |
Output is correct |
| 5 |
Correct |
32 ms |
748 KB |
Output is correct |
| 6 |
Correct |
5 ms |
492 KB |
Output is correct |
| 7 |
Correct |
7 ms |
492 KB |
Output is correct |
| 8 |
Correct |
7 ms |
492 KB |
Output is correct |
| 9 |
Correct |
8 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
7020 KB |
Output is correct |
| 2 |
Correct |
36 ms |
7020 KB |
Output is correct |
| 3 |
Correct |
621 ms |
6428 KB |
Output is correct |
| 4 |
Correct |
24 ms |
748 KB |
Output is correct |
| 5 |
Correct |
7 ms |
492 KB |
Output is correct |
| 6 |
Correct |
7 ms |
492 KB |
Output is correct |
| 7 |
Correct |
7 ms |
492 KB |
Output is correct |
| 8 |
Correct |
2288 ms |
13788 KB |
Output is correct |
| 9 |
Correct |
2280 ms |
13796 KB |
Output is correct |
