#include"holiday.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
const int TREE_SIZE=1<<17;
struct SegTree{
int ch1,ch2;
ll sum; // sum of active
int num; // num of active
};
SegTree trees[2000000];
int ct;
int alloc_segtree(){
trees[ct].sum=0;
trees[ct].num=0;
trees[ct].ch1=-1;
trees[ct].ch2=-1;
return ct++;
}
ll get_sum(int node){
if(node==-1)
return 0;
return trees[node].sum;
}
int get_num(int node){
if(node==-1)
return 0;
return trees[node].num;
}
int activate(int node,int idx,int val,int rl,int rr){
int node2=alloc_segtree();
trees[node2].ch1=trees[node].ch1;
trees[node2].ch2=trees[node].ch2;
if(rl==rr-1){
trees[node2].sum=val;
trees[node2].num=1;
return node2;
}
int mid=(rl+rr)/2;
if(idx<mid){
if(trees[node2].ch1==-1)
trees[node2].ch1=alloc_segtree();
trees[node2].ch1=activate(trees[node2].ch1,idx,val,rl,mid);
}else{
if(trees[node2].ch2==-1)
trees[node2].ch2=alloc_segtree();
trees[node2].ch2=activate(trees[node2].ch2,idx,val,mid,rr);
}
trees[node2].sum=get_sum(trees[node2].ch1)+get_sum(trees[node2].ch2);
trees[node2].num=get_num(trees[node2].ch1)+get_num(trees[node2].ch2);
return node2;
}
// get sum of biggest k cities
ll get(int node,int k,int rl,int rr){
k=min(k,get_num(node));
if(k==0)
return 0;
if(k==get_num(node))
return get_sum(node);
int mid=(rl+rr)/2;
if(get_num(trees[node].ch1)<=k)
return get_sum(trees[node].ch1)+get(trees[node].ch2,k-get_num(trees[node].ch1),mid,rr);
return get(trees[node].ch1,k,rl,mid);
}
vector<int>gen_trees(vector<int>arr){
ct=0;
int n=(int)arr.size();
vector<pair<int,int>>sorted(n);
for(int i=0;i<n;i++)
sorted[i]={arr[i],i};
sort(sorted.begin(),sorted.end());
reverse(sorted.begin(),sorted.end());
vector<int>in_sorted(n);
for(int i=0;i<n;i++)
in_sorted[sorted[i].second]=i;
vector<int>trees;
trees.push_back(alloc_segtree());
for(int i=0;i<n;i++)
trees.push_back(activate(trees.back(),in_sorted[i],sorted[in_sorted[i]].first,0,TREE_SIZE));
return trees;
}
vector<ll>res3;
vector<int>trees3;
void gen3(int l,int r,int tl,int tr){
int d=(l+r)/2;
// r = how far you go
ll res=0;
int mid=0;
for(int r=tl;r<=d&&r<=tr;r++){
// c = how many cities you actually visit
int c=d-r;
ll curr=get(trees3[r],c,0,TREE_SIZE);
if(curr>res){
res=curr;
mid=r;
}
}
res3[d]=res;
if(l<r-1){
gen3(l,d,tl,mid);
gen3(d,r,mid,tr);
}
}
// if you can only walk in one direction
// return a[d] = most score if you have d days
vector<ll>get3(vector<int>arr){
int n=(int)arr.size();
trees3=gen_trees(arr);
res3.resize(2*n+1);
gen3(0,2*n+1,0,(int)trees3.size()-1);
return res3;
}
vector<ll>res2;
vector<int>trees2;
void gen2(int l,int r,int tl,int tr){
int d=(l+r)/2;
// r = how far you go
ll res=0;
int mid=0;
for(int r=tl;2*(r-1)<=d&&r<=tr;r++){
// c = how many cities you actually visit
int c=d-2*(r-1);
ll curr=get(trees2[r],c,0,TREE_SIZE);
if(curr>res){
res=curr;
mid=r;
}
}
res2[d]=res;
if(l<r-1){
gen2(l,d,tl,mid);
gen2(d,r,mid,tr);
}
}
// if you can only walk in one direction and have to go back
// return a[d] = most score if you have d days
vector<ll>get2(vector<int>arr){
int n=(int)arr.size();
trees2=gen_trees(arr);
res2.resize(3*n+1);
gen2(0,3*n+1,0,(int)trees2.size()-1);
return res2;
}
// if you first start walking to the left and then right
ll get1(vector<int>arr,int d,int s){
int n=(int)arr.size();
vector<int>arr1,arr2;
for(int i=s;i>=0;i--)
arr1.push_back(arr[i]);
for(int i=s+1;i<n;i++)
arr2.push_back(arr[i]);
vector<ll>val1=get2(arr1),val2=get3(arr2);
ll res=0;
for(int d1=0;d1<=d;d1++){
int d2=d-d1;
res=max(res,val1[min(d1,(int)val1.size()-1)]+val2[min(d2,(int)val2.size()-1)]);
}
return res;
}
ll findMaxAttraction(int n,int start,int d,int attraction[]){
vector<int>arr;
for(int i=0;i<n;i++)
arr.push_back(attraction[i]);
ll res=get1(arr,d,start);
reverse(arr.begin(),arr.end());
return max(res,get1(arr,d,n-start-1));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
266 ms |
58900 KB |
Output is correct |
| 2 |
Correct |
134 ms |
58880 KB |
Output is correct |
| 3 |
Correct |
265 ms |
58656 KB |
Output is correct |
| 4 |
Correct |
139 ms |
58612 KB |
Output is correct |
| 5 |
Correct |
479 ms |
54164 KB |
Output is correct |
| 6 |
Correct |
125 ms |
18336 KB |
Output is correct |
| 7 |
Correct |
245 ms |
31076 KB |
Output is correct |
| 8 |
Correct |
310 ms |
38500 KB |
Output is correct |
| 9 |
Correct |
79 ms |
13348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3164 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3160 KB |
Output is correct |
| 4 |
Correct |
9 ms |
3164 KB |
Output is correct |
| 5 |
Correct |
10 ms |
3164 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3140 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
268 ms |
55768 KB |
Output is correct |
| 2 |
Correct |
497 ms |
59300 KB |
Output is correct |
| 3 |
Correct |
186 ms |
21576 KB |
Output is correct |
| 4 |
Correct |
9 ms |
3164 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
507 ms |
33172 KB |
Output is correct |
| 9 |
Correct |
463 ms |
33184 KB |
Output is correct |
