QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722364 | #7787. Maximum Rating | hanmx | WA | 0ms | 3632kb | C++17 | 5.0kb | 2024-11-07 18:44:16 | 2024-11-07 18:44:16 |
Judging History
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'