| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 379074 | leinad2 | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
struct node
{
int l, r, v;
long long sum;
}nd;
node pst[2000010];
map<int, int>x;
map<int, int>::iterator it;
int t, n, q, a, b, c, i, j, sz, d, rt, cnt, root[100010], opt[100010], X[100010], A[100010], st;
long long dap=-1e18;
void make_node(){pst[sz++]={-1, -1, 0, 0};}
void init(int id, int s, int e)
{
if(s==e)return;
int m=s+e>>1;
if(pst[id].l==-1)
{
pst[id].l=sz;
make_node();
}
init(pst[id].l, s, m);
if(pst[id].r==-1)
{
pst[id].r=sz;
make_node();
}
init(pst[id].r, m+1, e);
}
void update(int prev, int id, int s, int e, int x)
{
pst[id].v=pst[prev].v+1;
pst[id].sum=pst[prev].sum+X[x];
if(s==e)return;
int m=s+e>>1;
if(x<=m)
{
pst[id].l=sz;
make_node();
pst[id].r=pst[prev].r;
update(pst[prev].l, pst[id].l, s, m, x);
}
else
{
pst[id].r=sz;
make_node();
pst[id].l=pst[prev].l;
update(pst[prev].r, pst[id].r, m+1, e, x);
}
}
long long get(int prev, int id, int s, int e, int k)
{
if(s==e)
{
if(X[s])return min(k, (int)(pst[id].sum-pst[prev].sum)/X[s])*X[s];
return 0;
}
long long d=pst[pst[id].r].sum-pst[pst[prev].r].sum;
int ee=pst[pst[id].r].v-pst[pst[prev].r].v;
int m=s+e>>1;
if(k<=ee)return get(pst[prev].r, pst[id].r, m+1, e, k);
else return d+get(pst[prev].l, pst[id].l, s, m, k-ee);
}
void dnc(int s, int e, int l, int r)
{
if(s>e)return;
int mid=s+e>>1;
long long ans=-1e18;
int pos;
for(int i=l;i<=r;i++)
{
if(d-(i+st-2*mid)<0)continue;
long long res=get(root[mid-1], root[max(st, i)], 1, cnt, min(i-mid+1, d-(i+st-2*mid)));
if(ans<res)
{
ans=res;
pos=i;
}
}
dap=max(dap, ans);
opt[mid]=pos;
dnc(s, mid-1, l, pos);
dnc(mid+1, e, pos, r);
}
void rev(int a, int b)
{
if(a>=b)return;
swap(A[a], A[b]);
rev(a+1, b-1);
}
long long findMaxAttraction(int n, int st, int d, vector<int>attraction)
{
for(i=0;i<n;i++)A[i+1]=attraction[i];
for(i=0;i++<n;)
{
x[A[i]]++;
}
for(it=x.begin();it!=x.end();it++)it->second=++cnt,X[cnt]=it->first;
make_node();
init(0, 1, cnt);
for(i=0;i++<n;)
{
A[i]=x[A[i]];
root[i]=sz;
make_node();
update(root[i-1], root[i], 1, cnt, A[i]);
}
dnc(1, st, 1, n);
sz=0;
make_node();
init(0, 1, cnt);
rev(1, n);
for(i=0;i++<n;)
{
root[i]=sz;
make_node();
update(root[i-1], root[i], 1, cnt, A[i]);
}
st=n+1-st;
dnc(1, st, 1, n);
return dap;
}