QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#705288#7787. Maximum Ratingxxk2006WA 1ms9764kbC++232.4kb2024-11-02 22:48:202024-11-02 22:48:21

Judging History

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

  • [2024-11-02 22:48:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9764kb
  • [2024-11-02 22:48:20]
  • 提交

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'