QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722364#7787. Maximum RatinghanmxWA 0ms3632kbC++175.0kb2024-11-07 18:44:162024-11-07 18:44:16

Judging History

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

  • [2024-11-07 18:44:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3632kb
  • [2024-11-07 18:44:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i64=long long;
using u64=unsigned long long;
template<class Info>
struct SegementTree{
    int n;
    vector<Info> info;
    SegementTree():n(0){}
    SegementTree(int n_,Info v_=Info()){
        init(n_,v_);
    }
    template<class T>
    SegementTree(vector<T> init_){
        init(init_);
    }
    void init(int n_,Info v_=Info()){
        init(vector(n_,v_));
    }
    template<class T>
    void init(vector<T> init_){
        n=init_.size()-1;
        info.assign((n+1)<<2,Info());
        function<void(int,int,int)> build=[&](int p,int l,int r){
            if(l==r){
                info[p]=init_[l];
                return;
            }
            int m=(l+r)/2;
            build(p*2,l,m);
            build(p*2+1,m+1,r);
            push_up(p);
        };
        build(1,1,n);
    }
    void push_up(int p){
        info[p]=info[p*2]+info[p*2+1];
    }
    void modify(int p,int l,int r,int x,const Info& u){
        if(l==r){
            info[p]=info[p]+u;
            return;
        }
        int m=(l+r)/2;
        if(x<=m) modify(p*2,l,m,x,u);
        else modify(p*2+1,m+1,r,x,u);
        push_up(p);
    }
    void modify(int p,const Info& u){
        modify(1,1,n,p,u);
    }
    Info query(int p,int l,int r,int st,int en){
        if(st<=l&&r<=en){
            return info[p];
        }
        int m=(l+r)/2;
        Info sum;
        if(st<=m) sum=sum+query(p*2,l,m,st,en);
        if(en>m) sum=sum+query(p*2+1,m+1,r,st,en);
        return sum; 
    }
    Info query(int l,int r){
        return query(1,1,n,l,r);
    }
    template<class F> 
    int findfirst(int p,int l,int r,int x,int y,F pre){
        if(l>y||r<x||!pre(info[p])){
            return -1;
        }
        if(l==r){
            return l;
        }
        int mid=(l+r)/2;
        int res=findfirst(p*2,l,mid,x,y,pre);
        if(res==-1){
            return findfirst(p*2+1,mid+1,r,x,y,pre);
        }
        return res;
    }
    template<class F> 
    int findfirst(int l,int r,F pre){
        return findfirst(1,1,n,l,r,pre);
    }
    template<class F> 
    int findlast(int p,int l,int r,int x,int y,F pre){
        if(l>y||r<x||!pre(info[p])){
            return -1;
        }
        if(l==r){
            return l;
        }
        int mid=(l+r)/2;
        int res=findlast(p*2+1,mid+1,r,x,y,pre);
        if(res==-1){
            return findlast(p*2,l,mid,x,y,pre);
        }
        return res;
    }
    template<class F> 
    int findlast(int l,int r,F pre){
        return findlast(1,1,n,l,r,pre);
    }
};
struct Info{
    int num=0;
    ll sum=0;
};
Info operator+(const Info &a,const Info &b){
    Info c;
    c.num=a.num+b.num;
    c.sum=a.sum+b.sum;
    return c;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    const int N=n+q;
    SegementTree<Info> seg(N+1);
    ll sum=0;
    vector<int> p;
    vector<int> a(n+1);
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<0) sum+=-a[i];
        else{
            cnt++;
            p.push_back(a[i]);
        }
    } 
    vector<pair<int,int>> ans(q+1);
    for(int i=1;i<=q;i++){
        int x,y;
        cin>>x>>y;
        ans[i]={x,y};
        if(y>0){
            p.push_back(y);
        }
    }
    auto b=p;
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    auto find=[&](Info &a)->bool{
        if(a.num>sum) return 1;
        return 0;
    };
    auto id=[&](int x)->int{
        return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
    };
    for(int i=0;i<cnt;i++){
        seg.modify(id(p[i]),{1,p[i]});
    }
    auto findfirst=[&](auto findfirst,int p,int l,int r,int x,int y,ll tar)->int{
        if(l>y||r<x||seg.info[p].sum<=tar){
            return -1;
        }
        if(l==r){
            return l;
        }
        int mid=(l+r)/2;
        int res=findfirst(findfirst,p*2,l,mid,x,y,tar);
        if(res==-1){
            res=findfirst(findfirst,p*2+1,mid+1,r,x,y,tar-seg.info[p*2].sum);
        }
        return res;
    };
    for(int i=1;i<=q;i++){
        auto [x,y]=ans[i];
        if(a[x]<0){
            sum+=a[x];
        }
        else{
            cnt--;
            seg.modify(id(a[x]),{-1,-a[x]});
        }
        a[x]=y;
        if(y<0){
            sum-=y;
        }
        else{
            cnt++;
            seg.modify(id(y),{1,y});
        }
        int p=findfirst(findfirst,1,1,N,1,N,sum);
        //cout<<p<<"\n";
        if(p==-1){
            cout<<seg.query(1,N).num+1<<"\n";
        }
        else{
            int val=seg.query(p,p).sum/seg.query(p,p).num;
            //cout<<"v: "<<val<<"\n";
            ll sum1=0;
            if(p!=1) sum1=seg.query(1,p-1).sum;
            ll z=seg.query(1,p).sum-sum1;
            int r=0;
            if(p!=1) r=seg.query(1,p-1).num;
            cout<<r+z/val<<"\n";
        }
    }
    return 0;
}

详细

Test #1:

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

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: -100
Wrong Answer
time: 0ms
memory: 3632kb

input:

3 5
1 2 3
3 4
2 -2
1 3
3 1
2 1

output:

1
2
1
2
2

result:

wrong answer 5th numbers differ - expected: '1', found: '2'