QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#670048#7787. Maximum RatingYshanqianRE 1ms7684kbC++202.8kb2024-10-23 20:20:102024-10-23 20:20:10

Judging History

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

  • [2024-10-23 20:20:10]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7684kb
  • [2024-10-23 20:20:10]
  • 提交

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

output:


result: