# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
832951 |
2023-08-21T17:03:29 Z |
ttamx |
Holiday (IOI14_holiday) |
C++14 |
|
875 ms |
17044 KB |
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<int,int,int,int> t4;
const int N=1e5+5;
const int D=250005;
const int K=1<<18;
const ll inf=1e18;
int n,d,st;
int a[N];
vector<pair<int,int>> vec;
int mp[N];
ll dp[4][D];
struct segtree{
ll val[K];
int freq[K];
void update(int l,int r,int i,int x,ll v,int f){
val[i]+=v;
freq[i]+=f;
if(l==r)return;
int m=(l+r)/2;
if(x<=m)update(l,m,i*2,x,v,f);
else update(m+1,r,i*2+1,x,v,f);
}
void update(int x,ll v,int f){
update(1,n,1,x,v,f);
}
ll query(int l,int r,int i,int k){
if(l==r)return k>0?val[i]:0;
int m=(l+r)/2;
if(freq[i*2+1]<k)return query(l,m,i*2,k-freq[i*2+1])+val[i*2+1];
return query(m+1,r,i*2+1,k);
}
ll query(int k){
return query(1,n,1,k);
}
}s;
void add(int i){
s.update(mp[i],a[i],1);
}
void del(int i){
s.update(mp[i],-a[i],-1);
}
void solver(int beg,int end,int id,int mul){
int last=beg-1;
queue<t4> q;
q.emplace(1,d,beg,end);
while(!q.empty()){
auto [l,r,optl,optr]=q.front();
q.pop();
if(l>r)continue;
int mid=(l+r)/2;
pair<ll,int> best(0,-1);
for(int i=optl;i<=optr;i++){
while(last<i)add(++last);
while(last>i)del(last--);
best=max(best,{s.query(mid-mul*abs(i-st)),i});
}
int opt;
tie(dp[id][mid],opt)=best;
q.emplace(l,mid-1,optl,opt);
q.emplace(mid+1,r,opt,optr);
}
while(last>beg-1)del(last--);
}
void solvel(int beg,int end,int id,int mul){
int last=end+1;
queue<t4> q;
q.emplace(1,d,beg,end);
while(!q.empty()){
auto [l,r,optl,optr]=q.front();
q.pop();
if(l>r)continue;
int mid=(l+r)/2;
pair<ll,int> best(0,-1);
for(int i=optr;i>=optl;i--){
while(last>i)add(--last);
while(last<i)del(last++);
best=max(best,{s.query(mid-mul*abs(i-st)),i});
}
int opt;
tie(dp[id][mid],opt)=best;
q.emplace(l,mid-1,opt,optr);
q.emplace(mid+1,r,optl,opt);
}
while(last<end+1)del(last++);
}
ll findMaxAttraction(int _n,int start,int _d,int _a[]) {
n=_n,d=_d,st=start+1;
for(int i=1;i<=n;i++){
a[i]=_a[i-1];
vec.emplace_back(a[i],i);
}
sort(vec.begin(),vec.end());
for(int i=0;i<n;i++)mp[vec[i].second]=i+1;
solver(st+1,n,0,2);
solvel(1,st-1,1,2);
solver(st,n,2,1);
solvel(1,st,3,1);
ll ans=0;
for(int i=0;i<=d;i++){
ans=max(ans,dp[0][i]+dp[3][d-i]);
ans=max(ans,dp[1][i]+dp[2][d-i]);
}
return ans;
}
Compilation message
holiday.cpp: In function 'void solver(int, int, int, int)':
holiday.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | auto [l,r,optl,optr]=q.front();
| ^
holiday.cpp: In function 'void solvel(int, int, int, int)':
holiday.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | auto [l,r,optl,optr]=q.front();
| ^
# |
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 |
0 ms |
724 KB |
Output is correct |
5 |
Correct |
0 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
0 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
621 ms |
13836 KB |
Output is correct |
2 |
Correct |
528 ms |
13868 KB |
Output is correct |
3 |
Correct |
616 ms |
13860 KB |
Output is correct |
4 |
Correct |
562 ms |
13836 KB |
Output is correct |
5 |
Correct |
728 ms |
11476 KB |
Output is correct |
6 |
Correct |
239 ms |
9708 KB |
Output is correct |
7 |
Correct |
401 ms |
6900 KB |
Output is correct |
8 |
Correct |
445 ms |
6880 KB |
Output is correct |
9 |
Correct |
217 ms |
12760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
1256 KB |
Output is correct |
2 |
Correct |
16 ms |
1248 KB |
Output is correct |
3 |
Correct |
19 ms |
1152 KB |
Output is correct |
4 |
Correct |
13 ms |
980 KB |
Output is correct |
5 |
Correct |
13 ms |
980 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
3 ms |
724 KB |
Output is correct |
8 |
Correct |
3 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
875 ms |
17044 KB |
Output is correct |
2 |
Correct |
668 ms |
17012 KB |
Output is correct |
3 |
Correct |
270 ms |
3384 KB |
Output is correct |
4 |
Correct |
11 ms |
920 KB |
Output is correct |
5 |
Correct |
3 ms |
724 KB |
Output is correct |
6 |
Correct |
3 ms |
724 KB |
Output is correct |
7 |
Correct |
3 ms |
724 KB |
Output is correct |
8 |
Correct |
774 ms |
7428 KB |
Output is correct |
9 |
Correct |
815 ms |
7492 KB |
Output is correct |