QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670027 | #7787. Maximum Rating | Yshanqian | WA | 1ms | 5872kb | C++20 | 2.8kb | 2024-10-23 20:17:28 | 2024-10-23 20:17:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define int long long
typedef pair<int, int> pii;
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 5e5 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
int n, q, fu, a[N];
vector<int> t;
int find(int x)
{
return lower_bound(t.begin(), t.end(), x) - t.begin();
}
struct node
{
int l, r, num, sum;
} tr[N << 5];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
tr[u].num = tr[u << 1].num + tr[u << 1 | 1].num;
}
void build(int u, int l, int r)
{
tr[u] = {l, r, 0, 0};
if (l == r)
return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int pos, int val, int add) // 单点修改
{
if (tr[u].l == tr[u].r)
{
tr[u].num += add;
tr[u].sum += val * add;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (pos <= mid)
modify(u << 1, pos, val, add);
else
modify(u << 1 | 1, pos, val, add);
pushup(u);
}
int ask(int u, int fu)
{
if (fu <= 0)
return 0;
if (tr[u].l == tr[u].r)
{
if (tr[u].num == 0)
return 0;
return min(tr[u].num, fu / (tr[u].sum / tr[u].num));
}
if (tr[u << 1].sum <= fu)
return tr[u << 1].num + ask(u << 1 | 1, fu - tr[u << 1].sum);
else
return ask(u << 1, fu);
}
void solve()
{
cin >> n >> q;
vector<pii> que(q + 2);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] > 0)
t.pb(a[i]);
else
fu += a[i];
}
for (int i = 1; i <= q; i++)
{
int x, k;
cin >> x >> k;
if (x > 0)
t.pb(x);
que[i] = {x, k};
}
sort(t.begin(), t.end());
t.erase(unique(t.begin(), t.end()), t.end());
int m = t.size();
build(1, 1, m);
for (int i = 1; i <= n; i++)
{
int x = a[i];
if (x > 0)
{
int pos = find(x);
modify(1, pos, x, 1);
}
}
for (int i = 1; i <= q; i++)
{
auto [x, k] = que[i];
int lst = a[x];
a[x] = k;
if (lst <= 0)
fu -= lst;
else
{
int pos = find(lst);
modify(1, pos, lst, -1);
}
if (k <= 0)
fu += k;
else
{
int pos = find(k);
modify(1, pos, k, 1);
}
cout << ask(1, -fu) + 1 << endl;
}
}
signed main()
{
Yshanqian;
int T;
T = 1;
// cin >> T;
for (int cases = 1; cases <= T; ++cases)
{
// cout<<"Case #"<<cases<<": ";
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5852kb
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: 0ms
memory: 5676kb
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: 5872kb
input:
1 1 1000000000 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
1 1 -1000000000 1 -1000000000
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5660kb
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:
946 65 252 410 915 592 983 487 343 899 809 432 586 587 139 464 804 84 476 699 504 149 579 352 375 856 545 166 140 657 568 509 275 710 873 430 537 879 301 1 298 970 923 510 984 642 55 879 941 344 464 788 917 994 571 610 491 442 926 101 986 840 624 613 425 345 816 423 275 221 317 113 386 116 469 260 4...
result:
ok 1000 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 5652kb
input:
1000 1000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000...
output:
500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 ...
result:
ok 1000 numbers
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 5624kb
input:
1000 1000 -485078954 -474724347 -284958745 -99994191 -853392841 -796786314 -87134718 -861459498 -982809180 -184620712 -618476092 -244916830 -349486182 -751407510 -874417202 -419521829 -888338757 -735353446 -426330733 -715383449 -48093437 -359419189 -474876639 -887614191 -157085227 -51186523 -4851821...
output:
2 3 4 5 6 7 8 9 10 11 12 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 51 52 53 54 55 56 57 58 59 60 60 61 62 63 64 65 65 66 67 68 69 70 71 72 73 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 88 89 90 91 92 92 93 94 95 96...
result:
wrong answer 747th numbers differ - expected: '505', found: '504'