이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"holiday.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cassert>
#include <queue>
#define SZ (1 << 17)
using namespace std;
typedef long long ll;
int val[100005], N, D, pos;
ll ans = 0;
struct ST { ll tot; int cnt; };
struct Segtree {
ST st[1<<18];
ST stc(ST a, ST b) {
return { a.tot + b.tot, a.cnt + b.cnt };
}
void seg_ins(int x, int op) {
int i = x + SZ;
st[i] = { st[i].tot + x*op, st[i].cnt + op };
for (; i > 1; i >>= 1) st[i>>1] = stc(st[i], st[i^1]);
}
// Sum of cnt largest items in segtree
ll seg_walk(int cnt) {
ll res = 0;
int cur = 1;
if (cnt > st[1].cnt) return st[1].tot;
while (cur < SZ) {
if (st[cur<<1|1].cnt > cnt) {
cur = cur<<1|1;
} else {
res += st[cur<<1|1].tot;
cnt -= st[cur<<1|1].cnt;
cur = cur<<1;
}
}
return res;
}
} st1;
void solve1(int lo, int hi, int l, int r) {
if (lo >= hi) return;
int mid = (lo + hi) / 2;
// Segtree already populated with hi to l-1
for (int x = hi-1; x >= mid; x--) {
st1.seg_ins(val[x], 1);
}
ll ov = -1; int op = -1;
for (int k = l; k < r; k++) {
st1.seg_ins(val[k], 1);
ll res = st1.seg_walk(D - (min(pos - mid, k - pos) + (k - mid)));
if (res > ov) {
ov = res;
op = k;
}
}
//printf("solve(%d, %d, %d, %d): optimal %d (%lld)\n", lo, hi, l, r, op, ov);
ans = max(ans, ov);
assert(op != -1);
for (int k = l; k < r; k++) st1.seg_ins(val[k], -1);
solve1(lo, mid, l, op+1);
for (int k = l; k < r; k++) st1.seg_ins(val[k], 1);
for (int x = hi-1; x >= mid; x--) st1.seg_ins(val[x], -1);
solve1(mid+1, hi, op, r);
for (int k = l; k < r; k++) st1.seg_ins(val[k], -1);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n, D = d, pos = start;
for (int i = 0; i < n; i++) val[i] = attraction[i];
solve1(0, start, start, n);
return ans;
}
# | 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... |