이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
const int maxn = 1e5+4;
int n, s, t, a[maxn], mp[maxn];
struct Node {
int sum = 0, cnt = 0;
Node operator + (const Node &A) const {
return {sum + A.sum, cnt + A.cnt};
}
} st[maxn*4];
void update(int id, int l, int r, int i, int v) {
if (id < 0 || id >= maxn * 4)
{
cout << 962006;
exit(0);
}
if (i < l || i > r) return;
if (l == r) {
// st[id] = {v, 1};
return;
}
int mid = (l+r)>>1;
update(id*2, l, mid, i, v);
update(id*2+1, mid+1, r, i, v);
// st[id] = st[id*2] + st[id*2+1];
}
Node get(int id, int l, int r, int a, int b) {
if (r < a || b < l) return {0, 0};
if (a <= l && r <= b) return st[id];
int mid = (l+r)>>1;
return get(id*2, l, mid, a, b) + get(id*2+1, mid+1, r, a, b);
}
int walk(int k) {
int id = 1, l = 0, r = n-1;
if (st[1].cnt <= k) {
return st[1].sum;
}
while (l < r) {
int mid = (l+r)>>1;
if (st[id*2].cnt >= k) {
id = id*2;
r = mid;
} else {
k -= st[id*2].cnt;
id = id*2+1;
l = mid+1;
}
}
return st[id].sum;
}
int findMaxAttraction(int32_t _n, int32_t _s, int32_t _t, int32_t _a[]) {
n = _n; s = _s; t = _t;
for (int i = 0; i < n; i++) {
a[i] = _a[i];
}
if (s == 0) {
vector<pair<int, int>> V;
for (int i = 0; i < n; i++) {
V.push_back({a[i], i});
}
sort(V.rbegin(), V.rend());
for (int i = 0; i < n; i++) {
mp[V[i].second] = i;
}
int res = 0;
for (int i = 0; t-i > 0; i++) {
// move 1 -> i, get sum of t - i maximum
update(1, 0, n-1, mp[i], a[i]);
res = max(res, walk(t-i));
}
return res;
}
return -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... |