#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,int 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,int 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<int,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<query>q;
q.push(query(0,d,start,n-1));
//cerr<<"work\n";
while(!q.empty()){
auto x=q.front();
q.pop();
if(x.st>x.en)continue;
int m=(x.st+x.en)/2;
if(cur>x.optl){
tr.reset(1,n+1,1);
cur=start;
}
while(cur<x.optl){
tr.upd(1,n+1,1,id[cur],attraction[cur]);
cur++;
}
pair<long long,int>opt={-1ll,-1};
for(int i=x.optl;i<=x.optr;i++){
tr.upd(1,n+1,1,id[cur],attraction[cur]);
cur++;
int 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(query(x.st,m-1,x.optl,opt.second));
q.push(query(m+1,x.en,opt.second,x.optr));
}
//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(query(0,d,0,start));
//cerr<<"work\n";
attraction[start]=0;
id[start]=1;
while(!q.empty()){
auto x=q.front();
q.pop();
if(x.st>x.en)continue;
int m=(x.st+x.en)/2;
if(cur<x.optr){
tr.reset(1,n+1,1);
cur=start;
}
while(cur>x.optr){
tr.upd(1,n+1,1,id[cur],attraction[cur]);
cur--;
}
pair<long long,int>opt={-1ll,-1};
for(int i=x.optr;i>=x.optl;i--){
tr.upd(1,n+1,1,id[cur],attraction[cur]);
cur--;
int 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(query(x.st,m-1,opt.second,x.optr));
q.push(query(m+1,x.en,x.optl,opt.second));
}
//for(int i=0;i<=d;i++)cerr<<dpl[i]<<" ";
//cerr<<"\n";
for(int i=0;i<=d;i++){
int 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++){
int left=d-i-abs(optl[i]-start);
if(left<0)break;
ans=max(ans,dpl[i]+dpr[left]);
}
//count start repititively rn
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];
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4936 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4956 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 |
7004 KB |
Output is correct |
| 7 |
Correct |
2 ms |
7004 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5064 ms |
9040 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1081 ms |
5352 KB |
Output is correct |
| 2 |
Correct |
566 ms |
5164 KB |
Output is correct |
| 3 |
Correct |
818 ms |
5208 KB |
Output is correct |
| 4 |
Correct |
354 ms |
5260 KB |
Output is correct |
| 5 |
Correct |
303 ms |
5220 KB |
Output is correct |
| 6 |
Correct |
17 ms |
7000 KB |
Output is correct |
| 7 |
Correct |
9 ms |
7004 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5008 KB |
Output is correct |
| 9 |
Correct |
9 ms |
7016 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5040 ms |
10324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
