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"holiday.h"
#include<algorithm>
using namespace std;
#define SZ 131072
#define N_ 100010
long long Res;
struct A{
int a, num;
bool operator <(const A &p)const{
return a < p.a;
}
}ord[N_];
struct ST{
long long Sum;
int C;
}IT[SZ*2+2];
int num[N_], N;
void Ins(int node, int b, int e, int x, int ck){
if (b == e){
if (ck == IT[node].C)return;
if (ck){
IT[node].C = 1;
IT[node].Sum = ord[b].a;
}
else{
IT[node].C = 0, IT[node].Sum = 0;
}
return;
}
int m = (b + e) >> 1;
if (x <= m)Ins(node * 2, b, m, x, ck);
else Ins(node * 2 + 1, m + 1, e, x, ck);
IT[node].Sum = IT[node * 2].Sum + IT[node * 2 + 1].Sum;
IT[node].C = IT[node * 2].C + IT[node * 2 + 1].C;
}
long long Gap(int node, int x){
if (IT[node].C <= x)return IT[node].Sum;
if (IT[node * 2 + 1].C >= x) return Gap(node * 2 + 1, x);
else return IT[node * 2 + 1].Sum + Gap(node * 2, x - IT[node * 2 + 1].C);
}
void DP(int st, int b, int e, int s, int l, int d){
if (b > e)return;
int m = (b + e) >> 1, i, t, x;
long long M = 0, S;
for (i = m; i <= e; i++)
Ins(1, 0, SZ-1, num[i], 1);
for (i = s; i <= l; i++){
Ins(1, 0, SZ-1, num[i], 1);
t = d - st - i + m + m;
if (t <= 0)break;
S = Gap(1, t);
if (M < S){
M = S, x = i;
}
}
if (Res < M)Res = M;
for (i = s; i <= l; i++)Ins(1, 0, SZ-1, num[i], 0);
DP(st, b, m - 1, s, x, d);
for (i = m; i <= e; i++)Ins(1, 0, SZ-1, num[i], 0);
for (i = s; i < x; i++)Ins(1, 0, SZ-1, num[i], 1);
DP(st, m + 1, e, x, l, d);
for (i = s; i < x; i++)Ins(1, 0, SZ-1, num[i], 0);
}
void Do(int st, int d){
int i;
DP(st, max(0, st - (d-1)/2), st, st, N - 1, d);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
int i;
N = n;
for (i = 0; i < n; i++){
ord[i].a = attraction[i];
ord[i].num = i;
}
sort(ord, ord + n);
for (i = 0; i < n; i++)num[ord[i].num] = i;
Do(start, d);
for (i = 0; i < n; i++)num[n - 1 - ord[i].num] = i;
Do(n - 1 - start, d);
return Res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |