| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1188776 | proplayer | Holiday (IOI14_holiday) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include<holiday.h>
using namespace std;
using ll = long long;
using ld = long double;
const int maxN = 1e6 + 5;
const int Mod = 1e9 + 7;
ll f[maxN],g[maxN],f0[maxN],g0[maxN];
int id[maxN],n,s,d,a[maxN],id0[maxN];
pair<int,ll> st[4 * maxN];
pair<int,ll> unite(pair<int,ll> x,pair<int,ll> y)
{
return {x.first + y.first,x.second + y.second};
}
void update(int id,int l,int r,int i,ll val)
{
if (i > r || i < l) return;
if (l == r)
{
st[id] = {st[id].first ^ 1,(st[id].first ^ 1) * val};
// cerr << l << " " << r << " " << val << " " << st[id].first << " " << st[id].second << "\n";
return;
}
int mid = (l + r) / 2;
update(id * 2,l,mid,i,val);
update(id * 2 + 1,mid + 1,r,i,val);
st[id] = unite(st[id * 2],st[id * 2 + 1]);
}
pair<int,ll> get(int id,int l,int r,int u,int v,int k)
{
if (l > r) return {0,0};
if (l > v || r < u) return {0,0};
if (l == r) return (k >= st[id].first ? st[id] : make_pair(0,0ll));
//if (u <= l && r <= v) return {0,0};
int mid = (l + r) / 2;
pair<int,ll> res = {0,0};
if (st[id * 2 + 1].first > k) res = get(id * 2 + 1,mid + 1,r,u,v,k);
else if (st[id * 2 + 1].first < k) res = unite(st[id * 2 + 1],get(id * 2,l,mid,u,v,k - st[id * 2 + 1].first));
else res = st[id * 2 + 1];
return res;
}
bool cmp(int x,int y)
{
return a[x] < a[y];
}
bool maximize(ll& x,ll y)
{
if (x < y)
{
x = y;
return true;
}
return false;
}
void calc(int l,int r,int u,int v)
{
if (u > v || l > r) return;
int mid = (l + r) / 2;
g[mid] = u;
int best = u;
for (int i = u;i <= v;++i)
{
update(1,1,n,id0[i],a[i]);
if (mid + s - i >= 0 && maximize(f[mid],get(1,1,n,1,n,mid + s - i).second))
{
g[mid] = i;
best = i;
}
}
for (int i = v;i >= best;--i) update(1,1,n,id0[i],a[i]);
calc(mid + 1,r,best,v);
for (int i = best - 1;i >= u;--i) update(1,1,n,id0[i],a[i]);
calc(l,mid - 1,u,best);
}
void calc0(int l,int r,int u,int v)
{
if (u > v || l > r) return;
int mid = (l + r) / 2;
g0[mid] = v;
int best = v;
for (int i = v;i >= u;--i)
{
update(1,1,n,id0[i],a[i]);
if (mid + i - s >= 0 && maximize(f0[mid],get(1,1,n,1,n,mid + i - s).second))
{
g0[mid] = i;
best = i;
}
}
//cerr << l << " " << r << " " << u << " " << v << " " << mid << " " << f0[mid] << " " << g0[mid] << "\n";
for (int i = u;i <= best;++i) update(1,1,n,id0[i],a[i]);
calc0(mid + 1,r,u,best);
for (int i = best + 1;i <= v;++i) update(1,1,n,id0[i],a[i]);
calc0(l,mid - 1,best,v);
}
ll findMaxAttraction(int N,int S,int D,int A[])
{
n = N;
s = S;
d = D;
for (int i = 1;i <= n;++i) a[i] = A[i];
fill(st,st + 4 * n + 1,make_pair(0,0));
sort(id + 1,id + n + 1,cmp);
for (int i = 1;i <= n;++i) id0[id[i]] = i;
fill(f,f + n + 1,-1e18);
fill(f0,f0 + n + 1,-1e18);
f[0] = f0[0] = f[1] = f0[1] = 0;
g[0] = s;
g[1] = s + 1;
calc(1,d,s + 1,n);
fill(st,st + 4 * n + 1,make_pair(0,0));
g0[0] = s;
g0[1] = s - 1;
calc0(1,d,1,s - 1);
//cerr << f0[2] << "\n";
ll ans = 0;
for (int i = 1;i <= d;++i)
{
ans = max(f0[i],ans);
ans = max(f[i],ans);
ans = max(f[i - 1] + a[s],ans);
ans = max(f0[i - 1] + a[s],ans);
if (d - i + s - g[i] >= 0) ans = max(f0[d - i + s - g[i]] + f[i],ans);
if (d - i + s - g[i] - 1 >= 0) ans = max(f0[d - i + s - g[i] - 1] + f[i] + a[s],ans);
if (d - i - s + g0[i] >= 0) ans = max(f[d - i - s + g0[i]] + f0[i],ans);
if (d - i - s + g0[i] - 1 >= 0) ans = max(f[d - i - s + g0[i] - 1] + f0[i] + a[s],ans);
}
//cout << ans;
return ans;
//cerr << ans << "\n";
}
//
//int main()
//{
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// //freopen("dp_advanced_f.inp","r",stdin);
// //freopen("dp_advanced_f.out","w",stdout);
// input();
// solve();
//}