QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#634389#7787. Maximum RatingNIGHTLOSRE 1ms8016kbC++173.2kb2024-10-12 17:12:352024-10-12 17:12:36

Judging History

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

  • [2024-10-12 17:12:36]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:8016kb
  • [2024-10-12 17:12:35]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long

using namespace std;

const int N = 4e5 + 5, INF = 1e9 + 5;
const ll MaxN = 1e18;

int n, q;
int a[N];
struct node
{
    int l, r;
    ll sum, v, cnt;
}tr[N * 10];
struct option
{
    int x, v;
}op[N];
ll sum; //负数的和
vector<int> nums;

int find(int x)
{
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

void pushup(int p)
{
    tr[p].cnt = tr[p * 2].cnt + tr[p * 2 + 1].cnt;
    tr[p].sum = tr[p * 2].sum + tr[p * 2 + 1].sum;
}

void build(int p, int l, int r)
{
    tr[p].l = l; tr[p].r = r;
    if(l == r)
    {
        tr[p].v = nums[l];
        tr[p].sum = 0;
        tr[p].cnt = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    pushup(p);
}

void update(int p, int x, int d)
{
    if(tr[p].l == tr[p].r)
    {
        tr[p].cnt += d;
        tr[p].sum = tr[p].cnt * tr[p].v;
        return;
    }
    int mid = (tr[p].l + tr[p].r) / 2;
    if(mid >= x) update(p * 2, x, d);
    else update(p * 2 + 1, x, d);
    pushup(p);
}

ll query(int p, int l, int r)
{
    if(r == 0) return -MaxN;
    if(tr[p].l >= l && tr[p].r <= r)
        return tr[p].sum;
    int mid = (tr[p].l + tr[p].r) / 2;
    ll res = 0;
    if(mid >= l) res += query(p * 2, l, r);
    if(mid < r) res += query(p * 2 + 1, l, r);
    return res;
}

int query_pos(int p, int l, int r)
{
    if(r == 0) return 0;
    if(tr[p].l >= l && tr[p].r <= r) return tr[p].cnt;
    int mid = (tr[p].l + tr[p].r) / 2;
    int res = 0;
    if(mid >= l) res += query_pos(p * 2, l, r);
    if(mid < r) res += query_pos(p * 2 + 1, l, r);
    return res;
}

int get(ll d)
{
    int ans;
    int l = 0, r = nums.size() - 1;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(query(1, 1, mid) + d <= 0)
        {
            ans = query_pos(1, 1, mid);
            l = mid + 1;
        }else
        {
            r = mid - 1;
        }

    }
    return ans;
}

signed main()
{
    nums.push_back(-INF);
    scanf("%lld%lld", &n, &q);
    for(int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &a[i]);
        if(a[i] > 0) nums.push_back(a[i]);
        if(a[i] < 0) sum += a[i];
    }

    for(int i = 1; i <= q; i ++ )
    {
        int x, v;
        scanf("%lld%lld", &x, &v);
        if(v > 0) nums.push_back(v);
        op[i] = {x, v};
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    build(1, 1, nums.size() - 1);

    for(int i = 1; i <= n; i ++ )
    {
        if(a[i] > 0)
            update(1, find(a[i]), 1);
    }

    for(int i = 1; i <= q; i ++ )
    {
        int x = op[i].x, v = op[i].v;
        if(a[x] > 0)
        {
            update(1, find(a[x]), -1ll);
        }else
        {
            sum -= a[x];
        }
        if(v > 0)
        {
            update(1, find(v), 1ll);
        }else
        {
            sum += v;
        }
        a[x] = v;
        int t = get(sum);
        //cout<<sum<<"***"<<endl;
        printf("%lld\n", t + 1ll);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 8008kb

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

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

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: