QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693233 | #7787. Maximum Rating | 123456zmy# | WA | 1ms | 5940kb | C++17 | 1.5kb | 2024-10-31 15:45:23 | 2024-10-31 15:45:23 |
Judging History
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'