이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mx = 1e5 + 5;
int n, d, st, pos[mx], A[mx]; pair<int, int> S[mx]; ll ans, F[2][2][mx], bit[mx][2];
void upd(int i, int type){
int val = S[i].first;
for (; i < mx; i += i & (-i))
bit[i][0] += type * val, bit[i][1] += type;
}
ll qry(int k){
ll ret = 0;
for (int pw = (1 << 17), pos = 0; pw; pw /= 2)
if (pos + pw < mx and bit[pos + pw][1] <= k){
pos += pw;
ret += bit[pos][0];
k -= bit[pos][1];
}
return ret;
}
void dnq(int l, int r, int distL, int distR, bool dir, bool rep){
if (l > r or distL > distR) return;
for (int i = distL; i <= distR; i++) upd(pos[i], -1);
int midD = (l + r) / 2, stopMid = -1;
for (int stop = distL; stop <= distR; stop++){
int visit = midD - (stop - st) * (rep ? 2 : 1);
upd(pos[stop], 1);
if (visit < 0) continue;
ll val = qry(visit);
if (val >= F[dir][rep][midD]){
F[dir][rep][midD] = val;
stopMid = stop;
}
}
for (int i = stopMid + 1; i <= distR; i++) upd(pos[i], -1);
dnq(l, midD - 1, distL, stopMid, dir, rep);
for (int i = stopMid + 1; i <= distR; i++) upd(pos[i], 1);
dnq(midD + 1, r, stopMid, distR, dir, rep);
}
void work(int start, int tmpA[], bool dir, bool rep){
for (int i = 0; i < n; i++){
A[i + 1] = tmpA[i];
S[i + 1] = {tmpA[i], i + 1};
}
sort(S + 1, S + n + 1, greater<pair<int, int>>());
for (int i = 1; i <= n; i++) pos[S[i].second] = i;
memset(bit, 0, sizeof(bit));
for (int i = start; i <= n; i++) upd(pos[i], 1);
st = start;
dnq(0, d, start, n, dir, rep);
}
ll findMaxAttraction(int tmpN, int start, int tmpD, int tmpA[]){
n = tmpN; d = tmpD; start++;
work(start, tmpA, 0, 0);
work(start + 1, tmpA, 0, 1);
reverse(tmpA, tmpA + n);
work(n - start + 1, tmpA, 1, 0);
work(n - start + 2, tmpA, 1, 1);
for (int i = 0; i <= d - 2; i++)
ans = max({ans, F[0][1][i] + F[1][0][d - i - 2], F[1][1][i], F[0][0][d - i - 2]});
return max({ans, F[0][0][d], F[1][0][d]});
}
# | 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... |