//source: usaco.guide IOI2014 holiday
//only run to evaluate memory used#include <bits/stdc++.h>
#include <bits/stdc++.h>
#include "holiday.h"
#define MAXS 3100000
#define MAX 100005
#define SEG3LIM (1000000007)
using ll = long long;
///If I don't use packed here I will get MLE
struct __attribute__((packed)) node {
int left;
int right;
ll sum;
int total;
};
///The idea is the following:
///I have a persistent seg3 that is able to do the folowing queries:
///What is the sum of the k biggest elements in the segment L-R (k,L nor R are constants)
///I need to answer those queries online
///After that I will use Divide And Conquer DP
///I will check which segment the guy will walk, how many visitations are left if he moves optimally
///(You can get his values with basic algebra) and TA-DA! Just use the function!
node memoria[MAXS];
int cur=1;
int alocar(void){
return cur++;
}
int sz;
node nodes[MAX];
ll vals[MAX];
///Insert element in persistent seg3
void inserir(node* x,ll val,int p,int la=0,int ra=SEG3LIM-1){
if(la==ra){
assert(p==la);
x->total++;
x->sum+=val;
return;
}
int m = (la+ra)/2;
if(m>=p){
auto old = x->left;
x->left=alocar();
memoria[x->left]=memoria[old];
inserir(&memoria[x->left],val,p,la,m);
}else {
auto old = x->right;
x->right=alocar();
memoria[x->right]=memoria[old];
inserir(&memoria[x->right],val,p,m+1,ra);
}
ll tot = 0,ss=0;
if(x->left)tot+=memoria[x->left].sum;
if(x->right)tot+=memoria[x->right].sum;
if(x->left)ss+=memoria[x->left].total;
if(x->right)ss+=memoria[x->right].total;
x->sum=tot;
x->total=ss;
}
///Query in persistent seg3
long long ans=0,limites,restante=0;
void walk(node* k,node* u,int la=0,int ra=SEG3LIM-1){
if(!restante||!(k->sum))return;
long long subsum=0,subtotal=0;
subsum+=u->sum;
subtotal+=u->total;
if(k->total-subtotal<=restante){
ans+=k->sum-subsum;
restante-=k->total-subtotal;
return;
}
int m=(la+ra)/2;
int tem = 0;
if(k->right){
tem=memoria[k->right].total-memoria[u->right].total;
}
if(la==ra){
ll pega = std::min(restante,k->total-subtotal);
restante-=pega;
ans+=((long long)la)*pega;
return;
}
if(la==ra)return;
walk(&memoria[k->right],&memoria[u->right],m+1,ra);
walk(&memoria[k->left],&memoria[u->left],la,m);
}
node locais[MAX];
///Setting up the persistent seg3
void prepara(void){
for(int i=0;i!=sz;++i){
if(i)locais[i]=locais[i-1];
///I believe that you can compress the coordinates here to reduce memory
///Wasn't necessary tho
inserir(&locais[i],vals[i],vals[i]);
}
}
///Main cost query (I mentioned above how it works). Complexity O(log N). Maybe you can
///get AC with O(log^2 N), the time limit is very generous, I only used around 6% of it.
long long consulta(int l,int r,int p){
ans=0;limites=1e7;restante=p;
auto beta = &locais[r],alpha=&memoria[0];
if(l){
alpha=&locais[l-1];
}
walk(beta,alpha);
return ans;
}
long long pode=0;
long long resp=0;
long long inicio=0;
///Here is our Divide and Conquer DP :)
void dp(int l,int r,int la,int ra){
if(r<l)return;
int m = (l+r)/2;
ll ans = 0,split=inicio;
for(int i=la;i<=ra;++i){
ll dist1=(inicio-i),dist2=(m-inicio);
///Formula to get optimal cost to travel segment [i,m] while starting in the beginning
ll custo = (std::min(dist1,dist2)*2)+std::max(dist1,dist2);
ll tem = pode-custo;
if(tem<=0)continue;
ll bonus = consulta(i,m,tem);
if(bonus>ans){
ans=bonus;
split=i;
}
}
resp=std::max(resp,ans);
dp(l,m-1,la,split);
dp(m+1,r,split,ra);
}
///Main function
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
sz=n;
for(int i=0;i!=n;++i){
vals[i]=attraction[i];
}
inicio=start;
pode=d;
prepara();
dp(inicio,n-1,0,inicio);
return resp;
}
Compilation message
holiday.cpp: In function 'void walk(node*, node*, int, int)':
holiday.cpp:73:9: warning: variable 'tem' set but not used [-Wunused-but-set-variable]
73 | int tem = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
668 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
62240 KB |
Output is correct |
| 2 |
Correct |
78 ms |
62320 KB |
Output is correct |
| 3 |
Correct |
60 ms |
62284 KB |
Output is correct |
| 4 |
Correct |
61 ms |
62208 KB |
Output is correct |
| 5 |
Correct |
76 ms |
57152 KB |
Output is correct |
| 6 |
Correct |
19 ms |
17916 KB |
Output is correct |
| 7 |
Correct |
35 ms |
32136 KB |
Output is correct |
| 8 |
Correct |
47 ms |
38728 KB |
Output is correct |
| 9 |
Correct |
13 ms |
13012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2516 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2516 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2460 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
62612 KB |
Output is correct |
| 2 |
Correct |
71 ms |
62856 KB |
Output is correct |
| 3 |
Correct |
80 ms |
28648 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2388 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
314 ms |
62800 KB |
Output is correct |
| 9 |
Correct |
309 ms |
62800 KB |
Output is correct |
