#include"holiday.h"
#include<bits/stdc++.h>
//#define int long long
using namespace std;
long long rvid[100005];
struct segtree{
long long info[400005];
long long freq[400005];
void upd(int st,int en,int i,int pos,long long val){
if(st>pos||en<pos)return;
//cerr<<"range:"<<st<<" "<<en<<"\n";
if(st==en)return info[i]+=val,freq[i]++,void();
int m=(st+en)/2;
upd(st,m,i*2,pos,val);
upd(m+1,en,i*2+1,pos,val);
info[i]=info[i*2]+info[i*2+1];
freq[i]=freq[i*2]+freq[i*2+1];
}
void un_upd(int st,int en,int i,int pos,long long val){
if(st>pos||en<pos)return;
if(st==en)return info[i]-=val,freq[i]-=1,void();
int m=(st+en)/2;
un_upd(st,m,i*2,pos,val);
un_upd(m+1,en,i*2+1,pos,val);
info[i]=info[i*2]+info[i*2+1];
freq[i]=freq[i*2]+freq[i*2+1];
}
long long fans(int st,int en,int i,long long pos){
//cerr<<"Range:"<<st<<" "<<en<<"\n";
if(st==en)return min(freq[i],pos)*(rvid[st]);
int m=(st+en)/2;
if(pos<=freq[i*2+1])return fans(m+1,en,i*2+1,pos);
else return fans(st,m,i*2,pos-freq[i*2+1])+info[i*2+1];
}
void reset(int st,int en,int i){
info[i]=0;
freq[i]=0;
if(st==en)return;
int m=(st+en)/2;
reset(st,m,i*2);
reset(m+1,en,i*2+1);
}
}tr;
vector<long long>v;
int id[100005];
long long dpl[100005];
long long dpr[100005];
int optl[100005];
int optr[100005];
map<long long,int>mp;
struct query{
int st,en,optl,optr;
query(int a,int b,int c,int d){
st=a,en=b,optl=c,optr=d;
}
};
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
for(int i=0;i<n;i++)if(!mp[attraction[i]])v.push_back(attraction[i]),mp[attraction[i]]++;
v.push_back(0);
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
for(int i=0;i<n+1;i++)id[i]=lower_bound(v.begin(),v.end(),attraction[i])-v.begin()+1;
long long ans=0;
int cur=start;
queue<pair<int,query>>q;
q.push({1,query(0,d,start,n-1)});
int cnt=0;
int curlv=1;
//cerr<<"work\n";
while(!q.empty()){
auto x=q.front().second;
int lv=q.front().first;
q.pop();
if(x.st>x.en)continue;
int m=(x.st+x.en)/2;
//cerr<<"cur:"<<cur<<"\n";
if(curlv<lv){
curlv++;
//cerr<<"reset\n";
cnt+=n;
tr.reset(1,n+1,1);
cur=start;
}
//cerr<<x.optl<<" "<<x.optr<<"\n";
while(cur<x.optl){
cnt++;
tr.upd(1,n+1,1,id[cur],attraction[cur]);
cur++;
}
pair<long long,long long>opt={-1ll,-1};
for(int i=x.optl;i<=x.optr;i++){
if(cur==i){
cnt++;
tr.upd(1,n+1,1,id[cur],attraction[cur]);
cur++;
}
long long left=m-abs(start-i);
long long x=tr.fans(1,n+1,1,left);
opt=max(opt,{x,i});
}
dpr[m]=opt.first;
optr[m]=opt.second;
//cerr<<x.st<<" "<<x.en<<" "<<m<<" "<<opt.first<<" "<<opt.second<<"\n";
q.push({lv+1,query(x.st,m-1,x.optl,opt.second)});
q.push({lv+1,query(m+1,x.en,opt.second,x.optr)});
}
//cerr<<"count:"<<cnt<<"\n";
//cerr<<"work\n";
//for(int i=0;i<=d;i++)cerr<<dpr[i]<<" ";
//cerr<<"\n";
tr.reset(1,n+1,1);
cur=start;
q.push({1,query(0,d,0,start)});
//cerr<<"work\n";
attraction[start]=0;
id[start]=1;
cnt=0;
curlv=1;
while(!q.empty()){
auto x=q.front().second;
int lv=q.front().first;
q.pop();
if(x.st>x.en)continue;
int m=(x.st+x.en)/2;
if(curlv<lv){
curlv++;
//cerr<<"reset\n";
cnt+=n;
tr.reset(1,n+1,1);
cur=start;
}
//cerr<<x.optr<<" "<<x.optl<<"\n";
while(cur>x.optr){
cnt++;
tr.upd(1,n+1,1,id[cur],attraction[cur]);
cur--;
}
//cerr<<"cur:"<<cur<<"\n";
pair<long long,long long>opt={-1ll,-1};
for(int i=x.optr;i>=x.optl;i--){
if(cur==i){
cnt++;
tr.upd(1,n+1,1,id[cur],attraction[cur]);
cur--;
}
long long left=m-abs(start-i);
long long x=tr.fans(1,n+1,1,left);
opt=max(opt,{x,i});
}
dpl[m]=opt.first;
optl[m]=opt.second;
//cerr<<x.st<<" "<<x.en<<" "<<m<<" "<<opt.first<<" "<<opt.second<<" "<<x.optl<<" "<<x.optr<<"\n";
q.push({lv+1,query(x.st,m-1,opt.second,x.optr)});
q.push({lv+1,query(m+1,x.en,x.optl,opt.second)});
}
//cerr<<"count:"<<cnt<<"\n";
//for(int i=0;i<=d;i++)cerr<<dpl[i]<<" ";
//cerr<<"\n";
for(int i=0;i<=d;i++){
long long left=d-i-abs(optr[i]-start);
if(left<0)break;
//cerr<<i<<" "<<left<<" "<<optr[i]<<" "<<dpr[i]+dpl[left]<<"\n";
ans=max(ans,dpr[i]+dpl[left]);
}
for(int i=0;i<=d/2;i++){
long long left=d-i-abs(optl[i]-start);
if(left<0)break;
ans=max(ans,dpl[i]+dpr[left]);
}
return ans;
}
Compilation message
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
11588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7260 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7004 KB |
Output is correct |
| 3 |
Correct |
7 ms |
7372 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5208 KB |
Output is correct |
| 5 |
Correct |
7 ms |
7256 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7004 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
118 ms |
22784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
