QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693233#7787. Maximum Rating123456zmy#WA 1ms5940kbC++171.5kb2024-10-31 15:45:232024-10-31 15:45:23

Judging History

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

  • [2024-10-31 15:45:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5940kb
  • [2024-10-31 15:45:23]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define M 1000000000
using namespace std;
int n,m,s,w;
int a[200001];
struct yu
{
    int l,r,sum,siz;
}f[10000001];
int tot,x,y;
void ins(int x,int l,int r,int o,int q)
{
    if (l==r)
    {
        f[x].sum+=q*o;
        f[x].siz+=q;
        return;
    }
    int mid=l+r>>1;
    if (mid>=o)
    {
        if (f[x].l==0)f[x].l=++tot;
        ins(f[x].l,l,mid,o,q);
    }
    else 
    {
        if (f[x].r==0)f[x].r=++tot;
        ins(f[x].r,mid+1,r,o,q);
    }
    f[x].sum=f[f[x].l].sum+f[f[x].r].sum;
    f[x].siz=f[f[x].l].siz+f[f[x].r].siz;
}
void find(int x,int l,int r,int s,int o)
{
    if (l==r)
    {
        if (s==0)printf("%lld\n",w-(n-o)+1);
        else
        {
            o+=(s+l-1)/l;
            printf("%lld\n",w-(n-o)+1);
        }
        return;
    }
    int mid=l+r>>1;
    if (f[f[x].l].sum>s)find(f[x].l,l,mid,s,o); else find(f[x].r,mid+1,r,s-f[f[x].l].sum,o+f[f[x].l].siz);
}
signed main()
{
    tot=1;
    scanf("%lld %lld",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if (a[i]<=0)s-=a[i];else ins(1,1,M,a[i],1);
    }
    while (m--)
    {
        scanf("%lld %lld",&x,&y);

        if (a[x]<=0)s+=a[x];else ins(1,1,M,a[x],-1);

        if (y<=0)s-=y;else ins(1,1,M,y,1);
        a[x]=y;

        w=f[1].siz;

        //printf("  %lld %lld\n",s,w);
        if (f[1].sum<=s)printf("%lld\n",f[1].siz+1);else
        find(1,1,M,s,0);
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5892kb

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

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

input:

1 1
1000000000
1 1000000000

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

1 1
-1000000000
1 -1000000000

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 5812kb

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:

945
64
251
409
914
591
982
486
342
898
808
431
585
586
138
463
803
83
475
698
503
148
578
351
374
855
544
165
139
656
567
508
274
709
872
429
536
878
300
0
297
969
922
509
983
641
54
878
940
343
463
787
916
993
570
609
490
441
925
100
985
839
623
612
424
344
815
422
274
220
316
112
385
115
468
259
4...

result:

wrong answer 1st numbers differ - expected: '946', found: '945'