#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;
}
for(i=1;i<=200000;i++)sum[i+1]=cnt[i+1]=0;
std::sort(b,b+n);
for(i=0;i<n;i++)c[b[i].second]=n-i;
qn=0;
q[qn].s=1;
q[qn].e=d;
q[qn].l=m;
q[qn].r=n-1;
qn++;
j=m-1;
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++;
}
return l[d];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
24396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
284 ms |
24400 KB |
Output is correct |
2 |
Correct |
276 ms |
24404 KB |
Output is correct |
3 |
Correct |
268 ms |
24400 KB |
Output is correct |
4 |
Correct |
280 ms |
24404 KB |
Output is correct |
5 |
Correct |
372 ms |
24396 KB |
Output is correct |
6 |
Correct |
116 ms |
24396 KB |
Output is correct |
7 |
Correct |
192 ms |
24400 KB |
Output is correct |
8 |
Correct |
228 ms |
24404 KB |
Output is correct |
9 |
Correct |
88 ms |
24400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
24400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
24396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |