이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int MAXN = 1e5 + 5;
int n, d, start, a[MAXN], root[MAXN];
long long ans = 0;
vector <int> cmp;
struct node_t {
int le, ri, cnt = 0;
long long sum = 0;
} it[100 * MAXN];
int Time;
void update(int pre, int nxt, int l, int r, int u, int val) {
if(l > u || r < u || l > r) return;
if(l == r) {
it[nxt].sum = it[pre].sum + 1LL * val * cmp[l - 1];
it[nxt].cnt = it[pre].cnt + val;
return;
}
int mid = l + r >> 1;
if(u <= mid) {
it[nxt].ri = it[pre].ri;
it[nxt].le = ++Time;
update(it[pre].le, it[nxt].le, l, mid, u, val);
} else {
it[nxt].le = it[pre].le;
it[nxt].ri = ++Time;
update(it[pre].ri, it[nxt].ri, mid + 1, r, u, val);
}
it[nxt].cnt = it[it[nxt].le].cnt + it[it[nxt].ri].cnt;
it[nxt].sum = it[it[nxt].le].sum + it[it[nxt].ri].sum;
}
long long getMax(int pre, int nxt, int l, int r, int cnt) {
if(cnt <= 0) return 0;
if(l == r) return 1LL * cnt * cmp[l - 1];
int mid = l + r >> 1;
int tmp = it[it[nxt].ri].cnt - it[it[pre].ri].cnt;
if(cnt <= tmp) return getMax(it[pre].ri, it[nxt].ri, mid + 1, r, cnt);
long long ans = it[it[nxt].ri].sum - it[it[pre].ri].sum;
ans += getMax(it[pre].le, it[nxt].le, l, mid, cnt - tmp);
return ans;
}
void divide_and_conquer(int l, int r, int u, int v) {
if(l > r) return;
int mid = l + r >> 1;
long long cost = -1;
int p = u;
for (int i = u; i <= v; ++i) {
int L = start - mid, R = i - start, cnt = d - L - R - min(L, R);
cnt = min(cnt, i - mid + 1);
if(cnt < 0) continue;
long long tmp = getMax(root[mid - 1], root[i], 1, n, cnt);
if(cost < tmp) {
cost = tmp;
p = i;
}
}
ans = max(ans, cost);
divide_and_conquer(l, mid - 1, u, p);
divide_and_conquer(mid + 1, r, p, v);
}
long long findMaxAttraction(int _n, int _start, int _d, int A[]) {
ans = Time = 0;
n = _n, d = _d, start = _start + 1;
for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
cmp = vector <int> (a + 1, a + n + 1);
sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin() + 1;
}
// for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];
for (int i = 1; i <= n; ++i) {
root[i] = ++Time;
update(root[i - 1], root[i], 1, n, a[i], 1);
}
divide_and_conquer(1, start, start, n);
return ans;
}
#ifdef LOCAL
#include<cstdio>
int main() {
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
int n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0 ; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(n, start, d, attraction));
return 0;
}
#endif // LOCAL
// Dream it. Wish it. Do it.
컴파일 시 표준 에러 (stderr) 메시지
holiday.cpp: In function 'void update(int, int, int, int, int, int)':
holiday.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid = l + r >> 1;
| ~~^~~
holiday.cpp: In function 'long long int getMax(int, int, int, int, int)':
holiday.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = l + r >> 1;
| ~~^~~
holiday.cpp: In function 'void divide_and_conquer(int, int, int, int)':
holiday.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = l + r >> 1;
| ~~^~~
# | 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... |