QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#389525 | #7622. Yet Another Coffee | wnsyou | WA | 1ms | 9732kb | C++17 | 1.6kb | 2024-04-14 15:03:54 | 2024-04-14 15:03:54 |
Judging History
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'