QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#247049#7622. Yet Another Coffeeucup-team896#WA 0ms9736kbC++142.4kb2023-11-11 13:17:522023-11-11 13:17:54

Judging History

你现在查看的是最新测评结果

  • [2023-11-11 13:17:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9736kb
  • [2023-11-11 13:17:52]
  • 提交

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'