| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 362720 | hoaphat1 | Fire (JOI20_ho_t5) | C++17 | 0 ms | 0 KiB |
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<bits/stdc++.h>
using namespace std;
long long findMaxAttraction(int n, int s, int d, int a[]) {
long long ans = 0;
long long now = 0;
int L = 0, R = -1;
vector<int> kt(n, 0);
priority_queue<pair<int, int>, vector<pair<int,int>> , greater<pair<int, int>>> pq;
priority_queue<pair<int, int>> smaller;
int sz = 0;
auto make_true = [&](int m) {
while (sz > m && !pq.empty()) {
auto x = pq.top();
pq.pop();
if (kt[x.second] != 1) continue;
kt[x.second] = 2;
now -= x.first;
smaller.push(x);
--sz;
}
while (sz < m && !smaller.empty()) {
auto x = smaller.top(); smaller.pop();
if (kt[x.second] != 2) continue;
kt[x.second] = 1;
now += x.first;
pq.push(x);
++sz;
}
};
auto add = [&](int id) {
int v = a[id];
pq.emplace(v, id);
now += v;
kt[id] = 1;
++sz;
};
auto del = [&](int id) {
int v = a[id];
if (kt[id] == 2) {
kt[id] = 0;
return ;
}
kt[id] = 0;
now -= v;
sz--;
};
auto moveL = [&](int l) {
while (L < l) del(L++);
while (L > l) add(--L);
};
auto moveR = [&](int r) {
while (R < r) add(++R);
while (R > r) del(R--);
};
function<void(int, int, int, int)> solve = [&](int l, int r, int L, int R) {
if (l > r) return ;
int mid = l + r >> 1;
int pos = -1;
moveR(L);
moveL(mid);
long long val = -1;
for (int i = L; i <= R; i++) {
moveR(i);
int lim = d - min(s - mid, i - s) - (i - mid);
make_true(lim);
if (val < now) {
val = now;
pos = i;
}
}
ans = max(ans, val);
solve(l, mid - 1, L, pos);
solve(mid + 1, r, pos, R);
};
function<void(int, int, int, int)> solve1 = [&](int l, int r, int L, int R) {
if (l > r) return ;
int mid = l + r >> 1;
int pos = -1;
moveR(L);
moveL(mid);
long long val = -1;
for (int i = L; i <= R; i++) {
moveR(i);
int lim = d - min(s - mid, i - s) - (i - mid);
make_true(lim);
if (val < now) {
val = now;
pos = i;
}
}
ans = max(ans, val);
solve1(mid + 1, r, pos, R);
solve1(l, mid - 1, L, pos);
};
solve(max(0, s - d), s, s, min(n - 1, s + d));
solve1(max(0, s - d), s, s, min(n - 1, s + d));
return ans;
}