QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#247049 | #7622. Yet Another Coffee | ucup-team896# | WA | 0ms | 9736kb | C++14 | 2.4kb | 2023-11-11 13:17:52 | 2023-11-11 13:17:54 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
const int N = 200010;
const int M = N * 30;
struct node {
int cnt;
ll sum;
friend node operator+(node x, node y) {
node res;
res.cnt = x.cnt + y.cnt, res.sum = x.sum + y.sum;
return res;
}
} t[M];
int n, m, a[N], id[N], ls[M], rs[M], rt[N], tot;
pii c[N];
ll sum[N], ans[N];
#define mid ((l + r) >> 1)
void upd(int &p, int q, int l, int r, int x, int v) {
p = ++tot, ls[p] = ls[q], rs[p] = rs[q];
if (l == r) return t[p] = t[q], t[p].cnt++, t[p].sum += v, void();
if (x <= mid) upd(ls[p], ls[q], l, mid, x, v);
else upd(rs[p], rs[q], mid + 1, r, x, v);
t[p] = t[ls[p]] + t[rs[p]];
}
ll qry(int p, int l, int r, int w) {
if (l == r) return t[p].sum;
if (w <= t[ls[p]].cnt) return qry(ls[p], l, mid, w);
else return qry(rs[p], mid + 1, r, w - t[ls[p]].cnt) + t[ls[p]].sum;
}
#undef mid
void solve(int l, int r, int ql, int qr) {
int mid = (l + r) >> 1;
pll res = pll(1e18, -1);
rep (i, ql, qr) {
if (i < mid) continue;
ll val = qry(rt[i], 1, n, mid) - sum[i];
res = min(res, pll(val, i));
}
ans[mid] = res.fi;
if (l != mid) solve(l, mid - 1, ql, res.se);
if (r != mid) solve(mid + 1, r, res.se, qr);
}
void work() {
cin >> n >> m;
rep (i, 1, n) cin >> a[i], sum[i] = 0;
rep (i, 1, m) {
int x, y;
cin >> x >> y;
sum[x] += y;
}
rep (i, 1, n) sum[i] += sum[i - 1];
rep (i, 1, n) c[i] = pii(a[i], i);
sort(c + 1, c + n + 1);
rep (i, 1, n) id[i] = lower_bound(c + 1, c + n + 1, pii(a[i], i)) - c;
rep (i, 1, tot) t[i] = (node){0, 0ll}, ls[i] = rs[i] = 0;
tot = 0;
rep (i, 1, n) upd(rt[i], rt[i - 1], 1, n, id[i], a[i]);
solve(1, n, 1, n);
rep (i, 1, n) cout << ans[i] << " ";
cout << "\n";
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
int t; cin >> t;
while (t--) work();
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9736kb
input:
5 10 14 17 37 59 65 53 73 68 177 160 111 10 177 5 193 2 30 3 63 2 339 3 263 5 178 2 190 9 23 10 328 10 200 9 8 3 391 6 230 12 9 152 306 86 88 324 59 18 14 42 260 304 55 3 50 2 170 1 252 7 811 1 713 7 215 10 201 4 926 8 319 19 20 182 74 180 201 326 243 195 31 170 263 284 233 48 166 272 281 179 116 31...
output:
-2596 -2559 -2506 -2447 -2382 -2314 -2241 -2130 -1970 -1793 -3643 -3625 -3583 -3528 -3469 -3383 -3295 -3143 -2883 -2579 -2273 -1949 -6678 -6630 -6556 -6440 -6274 -6104 -5925 -5745 -5563 -5368 -5167 -4934 -4691 -4428 -4156 -3875 -3591 -3272 -2946 -3418 -3003 -2572 -2140 -1707 -1238 -768 -274 243 1...
result:
wrong answer 11th numbers differ - expected: '-3505', found: '-3643'