#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+6;
const int MAXT=3e5+6;
const ll INF=2e13;
ll att[MAXN];
ll low[MAXT],high[MAXT],n1,start1,d1;
priority_queue<ll> pq;
ll cur_sum;
ll fr[MAXT],ansr[MAXT];
ll fl[MAXT],ansl[MAXT];
//start1 will be in left
vector<ll> what_to_check[MAXN];
struct node
{
ll cnt_cities;
ll sum;
};
struct segment_tree
{
node tree[3*MAXN];
void init()
{
for(ll j=0;j<3*MAXN;j++)
{
tree[j].cnt_cities=0;
tree[j].sum=0;
}
}
void update(ll l,ll r,ll idx,ll pos,ll val)
{
if(l>pos)return;
if(r<pos)return;
if(l==r)
{
tree[idx].cnt_cities=1;
tree[idx].sum=val;
return;
}
ll mid=(l+r)/2;
update(l,mid,idx*2,pos,val);
update(mid+1,r,idx*2+1,pos,val);
tree[idx].cnt_cities=tree[idx*2].cnt_cities+tree[idx*2+1].cnt_cities;
tree[idx].sum=tree[idx*2].sum+tree[idx*2+1].sum;
}
ll query(ll l,ll r,ll idx,ll cnt_needed)
{
if(cnt_needed<0)return -INF;
if(cnt_needed==0)return 0;
if(cnt_needed>=tree[idx].cnt_cities)return tree[idx].sum;
//cout<<l<<" "<<r<<" "<<tree[idx].cnt_cities<<" "<<cnt_needed<<endl;
ll mid=(l+r)/2;
if(tree[idx*2+1].cnt_cities>=cnt_needed)return query(mid+1,r,idx*2+1,cnt_needed);
else return tree[idx*2+1].sum+query(l,mid,idx*2,cnt_needed-tree[idx*2+1].cnt_cities);
}
}tr;
ll num[MAXN];
void compute_right(ll factor)
{
ll max_time=(n1-start1)*factor+(n1-start1);
vector<pair<ll,ll> >llervals;
vector<pair<ll,ll> >new_llervals;
llervals.push_back({0,max_time});
for(;llervals.size()>0;)
{
//memset(what_to_check,-1,sizeof(what_to_check));
//cout<<"??1\n";
for(auto xd:llervals)
{
ll mid=(xd.first+xd.second)/2;
if(xd.first-1>=0)low[mid]=ansr[xd.first-1];
else low[mid]=start1;
if(xd.second+1<=max_time)high[mid]=ansr[xd.second+1];
else high[mid]=n1;
//cout<<mid<<" "<<low[mid]<<" "<<high[mid]<<endl;
for(ll j=low[mid];j<=high[mid];j++)
{
//cout<<"*"<<j<<endl;
what_to_check[j].push_back(mid);
}
}
//cout<<"??2\n";
tr.init();
for(ll i=start1;i<=n1;i++)
{
if(i!=start1)tr.update(1,n1,1,num[i],att[i]);
for(auto time1:what_to_check[i])
{
if(time1==-1)continue;
ll gg=tr.query(1,n1,1,time1-(i-start1)*factor);
//cout<<"update right"<<time1<<" "<<gg<<endl;
if(gg>fr[time1])
{
fr[time1]=gg;
ansr[time1]=i;
}
}
what_to_check[i].clear();
}
//cout<<"??3\n";
new_llervals.clear();
for(auto xd:llervals)
{
ll mid=(xd.first+xd.second)/2;
if(xd.first==xd.second)continue;
if(xd.first<=mid-1)new_llervals.push_back({xd.first,mid-1});
if(mid+1<=xd.second)new_llervals.push_back({mid+1,xd.second});
}
llervals=new_llervals;
}
}
void compute_left(ll factor)
{
ll max_time=(start1-1)*factor+start1;
vector<pair<ll,ll> >llervals;
vector<pair<ll,ll> >new_llervals;
llervals.push_back({0,max_time});
for(;llervals.size()>0;)
{
//memset(what_to_check,-1,sizeof(what_to_check));
for(auto xd:llervals)
{
ll mid=(xd.first+xd.second)/2;
if(xd.second+1<=max_time)low[mid]=ansl[xd.second+1];
else low[mid]=1;
if(xd.first-1>=0)high[mid]=ansl[xd.first-1];
else high[mid]=start1;
//cout<<"aloo "<<mid<<" "<<low[mid]<<" "<<high[mid]<<endl;
for(ll j=low[mid];j<=high[mid];j++)
{
what_to_check[j].push_back(mid);
}
}
tr.init();
for(ll i=start1;i>=1;i--)
{
tr.update(1,n1,1,num[i],att[i]);
for(auto time1:what_to_check[i])
{
if(time1==-1)continue;
//cout<<"%% "<<i<<" "<<time1<<endl;
//cout<<time1-(start1-i)*factor<<endl;
ll gg=tr.query(1,n1,1,time1-(start1-i)*factor);
//cout<<"update left"<<time1<<" "<<gg<<endl;
if(gg>fl[time1])
{
fl[time1]=gg;
ansl[time1]=i;
}
}
what_to_check[i].clear();
}
new_llervals.clear();
for(auto xd:llervals)
{
ll mid=(xd.first+xd.second)/2;
//cout<<"^^ "<<mid<<" "<<fl[mid]<<" "<<ansl[mid]<<endl;
if(xd.first==xd.second)continue;
if(xd.first<=mid-1)new_llervals.push_back({xd.first,mid-1});
if(mid+1<=xd.second)new_llervals.push_back({mid+1,xd.second});
}
llervals=new_llervals;
}
}
ll solve_right()
{
memset(fl,-1,sizeof(fl));
memset(fr,-1,sizeof(fr));
compute_right(2);
compute_left(1);
ll ret=0;
ll mx=0;
for(ll t1=d1;t1>=0;t1--)
{
if(d1-t1<0)continue;
mx=max(mx,fr[d1-t1]);
if(fl[t1]<0)continue;
//if(fr[d1-t1]<0)continue;
//cout<<t1<<" "<<fl[t1]<<" "<<mx<<endl;
ret=max(ret,fl[t1]+mx);
//cout<<t1<<" "<<fl[t1]<<" "<<fr[d1-t1]<<endl;
}
return ret;
}
ll solve_left()
{
memset(fl,-1,sizeof(fl));
memset(fr,-1,sizeof(fr));
compute_right(1);
compute_left(2);
ll ret=0,mx=0;
for(ll t1=d1;t1>=0;t1--)
{
if(d1-t1<0)continue;
mx=max(mx,fr[d1-t1]);
if(fl[t1]<0)continue;
//if(fr[d1-t1]<0)continue;
ret=max(ret,fl[t1]+mx);
//cout<<t1<<" "<<fl[t1]<<" "<<mx<<endl;
}
return ret;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<pair<ll,ll> >by_value;
for(ll i=0;i<n;i++)
{
att[i+1]=attraction[i];
by_value.push_back({att[i+1],i+1});
}
sort(by_value.begin(),by_value.end());
for(ll i=0;i<by_value.size();i++)
{
num[by_value[i].second]=i+1;
}
n1=n;start1=start;d1=d;
start1++;
return max(solve_left(), solve_right());
}
Compilation message
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:214:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
214 | for(ll i=0;i<by_value.size();i++)
| ~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
12372 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12372 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12408 KB |
Output is correct |
| 4 |
Correct |
9 ms |
12372 KB |
Output is correct |
| 5 |
Correct |
9 ms |
12472 KB |
Output is correct |
| 6 |
Correct |
10 ms |
12416 KB |
Output is correct |
| 7 |
Correct |
10 ms |
12372 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
569 ms |
32388 KB |
Output is correct |
| 2 |
Correct |
458 ms |
34128 KB |
Output is correct |
| 3 |
Correct |
557 ms |
32520 KB |
Output is correct |
| 4 |
Correct |
468 ms |
34068 KB |
Output is correct |
| 5 |
Correct |
777 ms |
32568 KB |
Output is correct |
| 6 |
Correct |
207 ms |
18108 KB |
Output is correct |
| 7 |
Correct |
389 ms |
22916 KB |
Output is correct |
| 8 |
Correct |
489 ms |
24928 KB |
Output is correct |
| 9 |
Correct |
150 ms |
16832 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
13064 KB |
Output is correct |
| 2 |
Correct |
23 ms |
12996 KB |
Output is correct |
| 3 |
Correct |
24 ms |
13052 KB |
Output is correct |
| 4 |
Correct |
28 ms |
12884 KB |
Output is correct |
| 5 |
Correct |
30 ms |
12948 KB |
Output is correct |
| 6 |
Correct |
16 ms |
12628 KB |
Output is correct |
| 7 |
Correct |
20 ms |
12628 KB |
Output is correct |
| 8 |
Correct |
20 ms |
12620 KB |
Output is correct |
| 9 |
Correct |
22 ms |
12612 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
589 ms |
31440 KB |
Output is correct |
| 2 |
Correct |
648 ms |
32036 KB |
Output is correct |
| 3 |
Correct |
350 ms |
20668 KB |
Output is correct |
| 4 |
Correct |
28 ms |
12880 KB |
Output is correct |
| 5 |
Correct |
20 ms |
12628 KB |
Output is correct |
| 6 |
Correct |
19 ms |
12620 KB |
Output is correct |
| 7 |
Correct |
18 ms |
12536 KB |
Output is correct |
| 8 |
Correct |
928 ms |
29112 KB |
Output is correct |
| 9 |
Correct |
930 ms |
29280 KB |
Output is correct |
