QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#669887#7787. Maximum RatingYshanqianWA 1ms5700kbC++203.0kb2024-10-23 19:57:182024-10-23 19:57:18

Judging History

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

  • [2024-10-23 19:57:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5700kb
  • [2024-10-23 19:57:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define endl "\n"
#define pb push_back
#define int long long
#define ll long long
#define lowbit(x) x & (-x)
typedef pair<int, int> pii;
#define LF(x) fixed << setprecision(x)
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 2e5 + 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() + 1;
}
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));
    }
    int mid = tr[u].l + tr[u].r >> 1;
    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 + 1);

    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() + 10;

    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, a[i], 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: 5656kb

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: 5644kb

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: 3812kb

input:

1 1
1000000000
1 1000000000

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5584kb

input:

1 1
-1000000000
1 -1000000000

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5700kb

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: 5632kb

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: 3648kb

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'