#include"holiday.h"
#include<algorithm>
#include<cstdio>
std::pair<int,int> b[100000];
int c[100000];
long long l[250001];
long long r[250001];
struct rec
{
int s;
int e;
int l;
int r;
} q[1000000];
int qn;
long long sum[200001];
int cnt[200001];
long long findMaxAttraction(int n,int m,int d,int a[])
{
long long te;
int i,j,k,p,t,tt,cut;
for(i=0;i<n;i++)
{
b[i].first=a[i];
b[i].second=i;
}
std::sort(b,b+n);
for(i=0;i<n;i++)c[b[i].second]=n-i;
for(i=1;i<=200000;i++)sum[i]=cnt[i]=0;
qn=0;
q[qn].s=1;
q[qn].e=d;
q[qn].l=m;
q[qn].r=n-1;
qn++;
j=m;
for(i=0;i<qn;i++)if(q[i].s<=q[i].e)
{
p=(q[i].s+q[i].e)/2;
while(j<q[i].l)
{
j++;
k=c[j];
while(k<=200000)
{
sum[k]+=a[j];
cnt[k]++;
k+=k&-k;
}
}
while(j>q[i].l)
{
k=c[j];
while(k<=200000)
{
sum[k]-=a[j];
cnt[k]--;
k+=k&-k;
}
j--;
}
k=0;
tt=p+m-j;
for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=tt)
{
tt-=cnt[k|(1<<t)];
k|=1<<t;
}
while(k)
{
l[p]+=sum[k];
k-=k&-k;
}
cut=j;
while(j<q[i].r)
{
j++;
k=c[j];
while(k<=200000)
{
sum[k]+=a[j];
cnt[k]++;
k+=k&-k;
}
k=0;
tt=p+m-j;
for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=tt)
{
tt-=cnt[k|(1<<t)];
k|=1<<t;
}
te=0;
while(k)
{
te+=sum[k];
k-=k&-k;
}
if(te>l[p])
{
l[p]=te;
cut=j;
}
}
q[qn].s=q[i].s;
q[qn].e=p-1;
q[qn].l=q[i].l;
q[qn].r=cut;
qn++;
q[qn].s=p+1;
q[qn].e=q[i].e;
q[qn].l=cut;
q[qn].r=q[i].r;
qn++;
}
for(i=1;i<=200000;i++)sum[i]=cnt[i]=0;
qn=0;
q[qn].s=1;
q[qn].e=d;
q[qn].l=0;
q[qn].r=m;
qn++;
j=m;
for(i=0;i<qn;i++)if(q[i].s<=q[i].e)
{
p=(q[i].s+q[i].e)/2;
while(j>q[i].r)
{
j--;
k=c[j];
while(k<=200000)
{
sum[k]+=a[j];
cnt[k]++;
k+=k&-k;
}
}
while(j<q[i].r)
{
k=c[j];
while(k<=200000)
{
sum[k]-=a[j];
cnt[k]--;
k+=k&-k;
}
j++;
}
k=0;
tt=p+j-m;
for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=tt)
{
tt-=cnt[k|(1<<t)];
k|=1<<t;
}
while(k)
{
r[p]+=sum[k];
k-=k&-k;
}
cut=j;
while(j>q[i].l)
{
j--;
k=c[j];
while(k<=200000)
{
sum[k]+=a[j];
cnt[k]++;
k+=k&-k;
}
k=0;
tt=p+j-m;
for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=tt)
{
tt-=cnt[k|(1<<t)];
k|=1<<t;
}
te=0;
while(k)
{
te+=sum[k];
k-=k&-k;
}
if(te>r[p])
{
r[p]=te;
cut=j;
}
}
q[qn].s=p+1;
q[qn].e=q[i].e;
q[qn].l=cut;
q[qn].r=q[i].r;
qn++;
q[qn].s=q[i].s;
q[qn].e=p-1;
q[qn].l=q[i].l;
q[qn].r=cut;
qn++;
}
te=0;
for(i=0;i<=d;i++)
{
if(d-2*i>=0)te=std::max(te,l[d-2*i]+r[i]);
if(d-2*i-1>=0)te=std::max(te,l[d-2*i]+r[i]+a[m]);
if(d-2*i>=0)te=std::max(te,r[d-2*i]+l[i]);
if(d-2*i-1>=0)te=std::max(te,r[d-2*i]+l[i]+a[m]);
}
return te;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
24400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
24404 KB |
Output is correct |
2 |
Correct |
284 ms |
24400 KB |
Output is correct |
3 |
Correct |
296 ms |
24396 KB |
Output is correct |
4 |
Correct |
308 ms |
24396 KB |
Output is correct |
5 |
Incorrect |
376 ms |
24400 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
24400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
292 ms |
24396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |