#include"holiday.h"
#include<string.h>
#include<algorithm>
using namespace std;
int ch,s,t=1,pos[100001],k,e[21],p2[250001];
long long dap,r1[250001],l1[250001],r2[250001],l2[250001],p[250001];
struct data{
int x,y;
bool operator<(const data&r)const{
return x>r.x;
}
}a[100001];
struct data2{
int num;
long long sum;
}tree[15][200010];
void update(int lev,int x,int s,int e,int k){
int mid=(s+e)/2;
if(s==e){
if(tree[lev][k].num==1){ch=1; return;}
tree[lev][k].num++, tree[lev][k].sum+=a[x].x; return;
}
if(x<=mid) update(lev,x,s,mid,k*2);
else update(lev,x,mid+1,e,k*2+1);
if(ch==0) tree[lev][k].num++, tree[lev][k].sum+=a[x].x;
}
void finding(int lev,int x,int y,int k,int num){
if(x==y){s=x-1; return;}
if(num-tree[lev][k*2].num>=0)
{
finding(lev,(x+y)/2+1,y,k*2+1,num-tree[lev][k*2].num);
}
else finding(lev,x,(x+y)/2,k*2,num);
}
long long query(int lev,int x,int y,int k,int s,int e){
if(s<=x && y<=e) return tree[lev][k].sum;
if(s>y || e<x) return 0;
return query(lev,x,(x+y)/2,k*2,s,e)+query(lev,(x+y)/2+1,y,k*2+1,s,e);
}
void gap(int m,int x,int y,int lev,int sw){
int i,ps=0;
long long maxi=0;
for(i=e[lev]+1;i<x;i++) update(lev,pos[i],1,t,1);
for(i=x;i<=y;i++)
{
ch=0; update(lev,pos[i],1,t,1);
if(sw==1) finding(lev,1,t+1,1,m-(i-1));
else finding(lev,1,t+1,1,m-(i-1)*2);
if(maxi<query(lev,1,t,1,1,s))
{
maxi=query(lev,1,t,1,1,s);
ps=i;
}
}
e[lev]=y;
p[m]=maxi; p2[m]=ps;
}
void pro(int m1,int m2,int x,int y,int lev,int sw){
int m=(m1+m2)/2;
gap(m,x,y,lev,sw);
if(m1==m2 || p2[m]==0) return;
pro(m1,(m1+m2)/2,x,p2[m],lev+1,sw);
pro((m1+m2)/2+1,m2,p2[m],y,lev+1,sw);
}
void init(){
int i;
for(i=0;i<=20;i++) e[i]=1;
memset(tree,0,sizeof tree);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
int i;
for(i=start;i>=0;i--) a[start-i+1].x=attraction[i], a[start-i+1].y=start-i+1;
t=start+1;
sort(a+1,a+start+2);
for(i=1;i<=(start+1);i++) pos[a[i].y]=i;
init(); pro(1,start*3,2,start+1,0,1);
for(i=1;i<=start*3;i++) l1[i]=p[i];
init(); pro(1,start*3,2,start+1,0,2);
for(i=1;i<=start*3;i++) l2[i]=p[i];
for(i=start;i<n;i++) a[i-start+1].x=attraction[i], a[i-start+1].y=i-start+1;
t=n-start;
sort(a+1,a+n-start+1);
for(i=1;i<=n-start;i++) pos[a[i].y]=i;
init(); pro(1,(n-start-1)*3,2,n-start,0,1);
for(i=1;i<=(n-start-1)*3;i++) r1[i]=p[i];
init(); pro(1,start*3,2,start+1,0,2);
for(i=1;i<=(n-start-1)*3;i++) r2[i]=p[i];
for(i=0;i<=d;i++){
if(dap<l1[i]+r2[d-i]) dap=l1[i]+r2[d-i];
if(dap<l2[i]+r1[d-i]) dap=l2[i]+r1[d-i];
if(i>=1 && dap<l1[i-1]+r2[d-i]+attraction[start]) dap=l1[i-1]+r2[d-i]+attraction[start];
if(i>=1 && dap<l2[i-1]+r1[d-i]+attraction[start]) dap=l2[i-1]+r1[d-i]+attraction[start];
}
return dap;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
60148 KB |
Output is correct |
| 2 |
Correct |
32 ms |
60152 KB |
Output is correct |
| 3 |
Correct |
24 ms |
60156 KB |
Output is correct |
| 4 |
Correct |
24 ms |
60152 KB |
Output is correct |
| 5 |
Incorrect |
20 ms |
60152 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
116 ms |
60152 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
60152 KB |
Output is correct |
| 2 |
Correct |
52 ms |
60148 KB |
Output is correct |
| 3 |
Correct |
56 ms |
60152 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
60152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
492 ms |
60144 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
