#include"holiday.h"
#include<algorithm>
std::pair<int,int> b[100000];
int c[100000];
long long l[200000];
long long r[200000];
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,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]=i+1;
qn=0;
q[qn].s=1;
q[qn].e=(n-d)*2-1;
q[qn].l=d;
q[qn].r=n-1;
qn++;
j=d-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;
for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=2*d-j)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;
for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=2*d-j)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 r[d];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
23620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
23620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
23624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
23624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
