QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #770961 | #7787. Maximum Rating | HQLF | WA | 2ms | 12052kb | C++20 | 4.5kb | 2024-11-22 05:27:49 | 2024-11-22 05:27:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ldb=long double;
const long long inf=0x3f3f3f3f3f3f3f3f;
const ll mod=1000000007;
struct node
{
ll l,r;
ll cnt;
ll sum;
}tree[2000010];
ll a[400010];
map<ll,ll>b;
ll num[400010];
pair<ll,ll>ask[400010];
map<ll,ll>wz;
ll ta[400010];
void build(ll s,ll t,ll p)
{
if(s==t)
{
tree[p].l=tree[p].r=s;
tree[p].cnt=ta[s];
tree[p].sum=ta[s]*num[s];
return;
}
ll mid=(s+t)>>1;
build(s,mid,p<<1);
build(mid+1,t,p<<1|1);
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
tree[p].cnt=tree[p<<1].cnt+tree[p<<1|1].cnt;
tree[p].l=tree[p<<1].l;tree[p].r=tree[p<<1|1].r;
}
void add(ll k,ll s,ll t,ll p)
{
if(k==s&&k==t)
{
tree[p].cnt++;
tree[p].sum+=num[s];
return;
}
else
{
ll mid=(s+t)>>1;
if(k<=mid)add(k,s,mid,p<<1);
else if(k>=mid+1)add(k,mid+1,t,p<<1|1);
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
tree[p].cnt=tree[p<<1].cnt+tree[p<<1|1].cnt;
tree[p].l=tree[p<<1].l;tree[p].r=tree[p<<1|1].r;
}
}
void erase(ll k,ll s,ll t,ll p)
{
if(k==s&&k==t)
{
tree[p].cnt--;
tree[p].sum-=num[s];
return;
}
else
{
ll mid=(s+t)>>1;
if(k<=mid)erase(k,s,mid,p<<1);
else if(k>=mid+1)erase(k,mid+1,t,p<<1|1);
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
tree[p].cnt=tree[p<<1].cnt+tree[p<<1|1].cnt;
tree[p].l=tree[p<<1].l;tree[p].r=tree[p<<1|1].r;
}
}
node getans(ll l,ll r,ll s,ll t,ll p)
{
if(l<=s&&r>=t)
{
return tree[p];
}
else
{
node ans;
ll mid=(s+t)>>1;
if(r<=mid)
{
ans=getans(l,r,s,mid,p<<1);
}
if(l>=mid+1)
{
ans=getans(l,r,mid+1,t,p<<1|1);
}
if(l<=mid&&r>=mid+1)
{
node x=getans(l,r,s,mid,p<<1);
node y=getans(l,r,mid+1,t,p<<1|1);
ans.sum=x.sum+y.sum;
ans.cnt=x.cnt+y.cnt;
ans.l=x.l;ans.r=y.r;
}
return ans;
}
}
void solve()
{
ll n,q;
cin>>n>>q;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>0)b[a[i]]++;
}
for(ll i=1;i<=q;i++)
{
ll x,v;
cin>>x>>v;
ask[i].first=x;
ask[i].second=v;
if(v>0)b[v]++;
}
ll ln=1;
for(auto[x,y]:b)
{
num[ln]=x;
ln++;
}
ln--;
for(ll i=1;i<=ln;i++)
{
wz[num[i]]=i;
}
ll ngsum=0;
for(ll i=1;i<=n;i++)
{
if(a[i]>0)
{
ta[wz[a[i]]]++;
}
else if(a[i]<0)
{
ngsum+=a[i];
}
}
if(ln==0)
{
for(ll i=1;i<=q;i++)
{
printf("1\n");
}
return;
}
build(1,ln,1);
for(ll i=1;i<=q;i++)
{
ll x=ask[i].first;
ll v=ask[i].second;
if(a[x]>0)
{
erase(wz[a[x]],1,ln,1);
}
else if(a[x]<0)
{
ngsum-=a[x];
}
if(v>0)
{
add(wz[v],1,ln,1);
}
else if(v<0)
{
ngsum+=v;
}
a[x]=v;
ll l=1,r=ln;
while(l<=r)
{
ll mid=(l+r)>>1;
node ans=getans(1,mid,1,ln,1);
if(llabs(ngsum)<ans.sum)
{
r=mid-1;
}
else if(llabs(ngsum)>=ans.sum)
{
l=mid+1;
}
}
//1--r <= llabs(ngsum)
if(r>=1)
{
if(r!=ln)
{
node ans=getans(1,r,1,ln,1);
ll cnt=getans(r+1,r+1,1,ln,1).cnt;
ll tx=(llabs(ngsum)-ans.sum)/num[r+1];
tx=min(tx,cnt);
ll tot=ans.cnt+tx;
ll as=tot+1;
printf("%lld\n",as);
}
else if(r==ln)
{
node all=getans(1,ln,1,ln,1);
ll as=all.cnt+1;
printf("%lld\n",as);
}
}
else if(r==0)
{
printf("1\n");
}
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
ll _=1;
// cin>>_;
while(_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12048kb
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: 2ms
memory: 12052kb
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: 11984kb
input:
1 1 1000000000 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7884kb
input:
1 1 -1000000000 1 -1000000000
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 11932kb
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:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer 1st numbers differ - expected: '946', found: '1'