QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670048 | #7787. Maximum Rating | Yshanqian | RE | 1ms | 7684kb | C++20 | 2.8kb | 2024-10-23 20:20:10 | 2024-10-23 20:20:10 |
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 + 11, 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()
{
fu = 0;
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 (k > 0)
t.pb(k);
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: 5580kb
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: 5584kb
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: 0ms
memory: 7684kb
input:
1 1 1000000000 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Runtime Error
input:
1 1 -1000000000 1 -1000000000