QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #681141 | #7787. Maximum Rating | XiaoYang3 | WA | 1ms | 7908kb | C++23 | 3.3kb | 2024-10-27 01:51:06 | 2024-10-27 01:51:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
using pii = pair<ll, ll>;
int P = 998244353;
ll n, na[N], nb[N], tot, ans, q, cnt;
struct node {
ll data;
ll sum, lazy;
} tree[N];
void pushup(int id, node* tree) {
tree[id].data = tree[id << 1].data + tree[id << 1 | 1].data;
tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
}
void change(int id, int l, int r, int x, int fg) {
if (l == r) {
if (fg) {
tree[id].data++;
tree[id].sum = tree[id].data * nb[l];
} else {
tree[id].data--;
tree[id].sum = tree[id].data * nb[l];
}
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
change(id << 1, l, mid, x, fg);
} else {
change(id << 1 | 1, mid + 1, r, x, fg);
}
pushup(id, tree);
}
void query(int id, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
ans += tree[id].sum;
cnt += tree[id].data;
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
query(id << 1, l, mid, ql, qr);
}
if (qr > mid) {
query(id << 1 | 1, mid + 1, r, ql, qr);
}
}
void solve() {
cin >> n >> q;
vector<pii> qy(q + 2);
ll sum0 = 0;
for (int i = 1; i <= n; i++) {
cin >> na[i];
if (na[i] > 0) {
nb[++tot] = na[i];
} else {
sum0 += na[i];
}
}
for (int i = 1; i <= q; i++) {
int x, v;
cin >> x >> v;
qy[i] = {x, v};
if (v > 0) {
nb[++tot] = v;
}
}
sort(nb + 1, nb + 1 + tot);
tot = unique(nb + 1, nb + 1 + tot) - nb - 1;
for (int i = 1; i <= n; i++) {
if (na[i] > 0) {
int k = lower_bound(nb + 1, nb + 1 + tot, na[i]) - nb;
change(1, 1, tot, k, 1);
}
}
for (int i = 1; i <= q; i++) {
auto [x, v] = qy[i];
if (na[x] <= 0) {
sum0 -= na[x];
if (v <= 0) {
sum0 += v;
} else {
int k = lower_bound(nb + 1, nb + 1 + tot, v) - nb;
change(1, 1, tot, k, 1);
}
} else {
int k = lower_bound(nb + 1, nb + 1 + tot, na[x]) - nb;
change(1, 1, tot, k, 0);
if (v <= 0) {
sum0 += v;
} else {
int k = lower_bound(nb + 1, nb + 1 + tot, v) - nb;
change(1, 1, tot, k, 1);
}
}
na[x] = v;
ll sum = abs(sum0);
if (sum >= tree[1].sum) {
cout << tree[1].data + 1 << '\n';
} else {
int l = 1, r = tot;
while (l <= r) {
int mid = (l + r) >> 1;
ans = 0;
query(1, 1, tot, 1, mid);
if (ans <= sum) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cnt = 0;
if (l != 1) {
query(1, 1, tot, 1, l - 1);
}
cout << cnt + 1 << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _;
_ = 1;
// cin >> _;
while (_--) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7716kb
input:
3 5 1 2 3 3 4 2 -2 1 -3 3 1 2 1
output:
1 2 2 2 3
result:
ok 5 number(s): "1 2 2 2 3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7656kb
input:
3 5 1 2 3 3 4 2 -2 1 3 3 1 2 1
output:
1 2 1 2 1
result:
ok 5 number(s): "1 2 1 2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7908kb
input:
1 1 1000000000 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7684kb
input:
1 1 -1000000000 1 -1000000000
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 7728kb
input:
1000 1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer 1st numbers differ - expected: '946', found: '1'