QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#389525#7622. Yet Another CoffeewnsyouWA 1ms9732kbC++171.6kb2024-04-14 15:03:542024-04-14 15:03:54

Judging History

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

  • [2024-04-14 15:03:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9732kb
  • [2024-04-14 15:03:54]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 10;

inline int lowbit (int x) {
  return x & -x;
}

struct coupon {
  int x, y;
  bool operator < (const coupon &i) const {
    return x < i.x;
  }
} c[N];

int T, n, m, a[N], tr[N];
ll ans, co[N], cst[N];
bool f[N];

void modify (int x) {
  if (x > n) {
    return ;
  }
  tr[x]++, modify(x + lowbit(x));
}

int Query (int x) {
  if (!x) {
    return 0;
  }
  return tr[x] + Query(x - lowbit(x));
}

void Solve () {
  set<pair<ll, int>> st;
  ans = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i], ans += a[i], cst[i] = -a[i], st.insert({cst[i], i}), tr[i] = f[i] = 0;
  }
  for (int i = 1; i <= m; i++) {
    cin >> c[i].x >> c[i].y, ans -= c[i].y;
  }
  sort(c + 1, c + m + 1);
  if (c[1].x == 1) {
    st.erase({cst[1], 1}), cst[1] += c[1].y, st.insert({cst[1], 1});
  }
  for (int i = n, j = 1, k = 2; i; i--) {
    co[i] = ans;
    auto del = *st.begin();
    f[del.second] = 1, ans += del.first, modify(del.second), st.erase(st.begin());
    bool ch = 0;
    while (j <= n && f[j]) {
      j++;
    }
    while (k <= m && c[k].x == Query(c[k].x)) {
      k++;
    }
    while (k <= m && c[k].x == Query(c[k].x) + 1) {
      if (!ch) {
        ch = 1, st.erase({cst[j], j});
      }
      cst[j] += c[k].y, k++;
    }
    if (ch) {
      st.insert({cst[j], j});
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << co[i] << ' ';
  }
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> T; T--; Solve(), cout << '\n') {}
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 9732kb

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 
-3505 -3491 -3473 -3431 -3376 -3317 -3231 -3143 -2883 -2579 -2273 -1949 
-6527 -6496 -6448 -6374 -6258 -6092 -5922 -5743 -5563 -5368 -5167 -4934 -4691 -4428 -4156 -3875 -3591 -3272 -2946 
-3219 -2987 -2572 -2140 -1707 -1238 -768 -274 243 1...

result:

ok 70 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 7780kb

input:

2
5 2
1 2 3 4 5
3 1
4 2
7 3
4 3 1 10 3 8 6
4 9
3 8
4 5

output:

-2 0 3 7 12 
-21 -18 -15 -11 -5 3 13 

result:

ok 12 numbers

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 7692kb

input:

8
1 0
72916
9 11
130289 240521 653024 625847 679075 529899 486802 540872 353600
2 5400
2 257841
6 48161
3 71484
9 156788
3 181910
4 45589
6 210869
5 70426
9 87059
5 115764
8 7
634608 412120 360938 425426 825551 138578 678304 747502
2 235317
4 281859
5 553042
8 295615
8 32014
8 755313
4 439284
19 10
...

output:

72916 
-1121002 -880481 -526881 -40079 489820 1030692 1656539 2309563 2988638 
-2231506 -2092928 -1680808 -1255382 -620774 57530 805032 1630583 
-1025384 -1022941 -1018403 -1013731 -1006580 -998875 -987675 -970496 -953098 -932654 -909692 -886331 -862054 -835158 -807901 -779123 -747157 -713222 -67928...

result:

wrong answer 11th numbers differ - expected: '-2180324', found: '-2231506'