QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#705288 | #7787. Maximum Rating | xxk2006 | WA | 1ms | 9764kb | C++23 | 2.4kb | 2024-11-02 22:48:20 | 2024-11-02 22:48:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define Enter putchar('\n')
#define spc putchar(' ')
#define pb push_back
#define fi first
#define se second
inline void read(int &num){num=0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}num*=f;}
inline void lread(long long &num){num=0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}num*=f;}
void print(long long num){if(num<0){putchar('-');num=-num;}if(num>9){print(num/10);}putchar((num%10)^48);}
const int N=2e5+9;
struct node{
int pos,v;
}ask[N];
int va[N],tong[N<<1],s[N<<2];
LL t[N<<2];
unordered_map<int,int> mp;
void cg(int p,int l,int r,int x,int y,int z){
if(l==r){
t[p]=y;
s[p]=z;
return;
}
int mid=l+r>>1;
if(x<=mid)cg(p<<1,l,mid,x,y,z);
else cg(p<<1|1,mid+1,r,x,y,z);
t[p]=t[p<<1]+t[p<<1|1];
s[p]=s[p<<1]+s[p<<1|1];
}
int query(int p,int l,int r,long long x){
if(l==r)return s[p];
int mid=l+r>>1;
if(t[p<<1|1]<x)return s[p<<1|1]+query(p<<1,l,mid,x-t[p<<1|1]);
return query(p<<1|1,mid+1,r,x);
}
int main(){
int n,Q,tot,cnt=0;
long long sum=0;
read(n),read(Q);
for(int i=1;i<=n;i++){
read(va[i]);
if(va[i]>0){
++tot;
tong[++cnt]=va[i];
}
sum+=va[i];
}
for(int i=1;i<=Q;i++){
read(ask[i].pos),read(ask[i].v);
if(ask[i].v>0)tong[++cnt]=ask[i].v;
}
sort(tong+1,tong+cnt+1);
int kt=unique(tong+1,tong+cnt+1)-tong-1;
for(int i=1;i<=kt;i++)mp[tong[i]]=i;
for(int i=1;i<=n;i++){
if(va[i]>0)cg(1,1,n,mp[va[i]],va[i],1);
}
//print(tot-query(1,1,n,sum)+1),Enter;
for(int i=1;i<=Q;i++){
sum-=va[ask[i].pos];
sum+=ask[i].v;
if(va[ask[i].pos]>0)--tot;
if(ask[i].v>0)++tot;
if(va[ask[i].pos]>0)cg(1,1,n,mp[va[ask[i].pos]],0,0);
if(ask[i].v>0)cg(1,1,n,mp[ask[i].v],ask[i].v,1);
va[ask[i].pos]=ask[i].v;
if(sum<=0){
print(tot+1),Enter;
continue;
}
print(tot-query(1,1,n,sum)+1),Enter;
}
return 0;
}
/*
3 3
1 -2 4
1 -3
3 1
2 1
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 9764kb
input:
3 5 1 2 3 3 4 2 -2 1 -3 3 1 2 1
output:
1600677167 1600677168 1600677168 1600677168 1600677169
result:
wrong answer 1st numbers differ - expected: '1', found: '1600677167'