#include<bits/stdc++.h>
using namespace std;
#define NN 100400
long long oo;
struct node{
long long l,r;
long long max,min;
long long sum;
long long fg;
}tree[NN*4];
long long n,q;
void Init(long long l,long long r,long long idd){
tree[idd].l=l;
tree[idd].r=r;
tree[idd].max=tree[idd].min=0;
tree[idd].sum=0;
tree[idd].fg=0;
if(r-l<=1) return ;
long long mid=(l+r)/2;
Init(l,mid,idd<<1);
Init(mid,r,idd<<1|1);
}
void Up(long long idd){
tree[idd].sum=tree[idd<<1].sum+tree[idd<<1|1].sum;
tree[idd].max=max(tree[idd<<1].max,tree[idd<<1|1].max);
tree[idd].min=min(tree[idd<<1].min,tree[idd<<1|1].min);
}
void Down(long long idd){
if(tree[idd].fg){
tree[idd<<1].fg=tree[idd<<1|1].fg=1;
tree[idd<<1].min=tree[idd<<1|1].min=tree[idd].min;
tree[idd<<1].max=tree[idd<<1|1].max=tree[idd].max;
tree[idd<<1].sum=tree[idd].min*(tree[idd<<1].r-tree[idd<<1].l);
tree[idd<<1|1].sum=tree[idd].min*(tree[idd<<1|1].r-tree[idd<<1|1].l);
tree[idd].fg=0;
}
}
long long u;
long long bg;
long long ssum;
long long ftt;
void Date(long long l,long long r,long long rr,long long num,long long pre,long long idd){
long long ssum=num+tree[idd].sum+ftt;
long long avg=ssum/(rr-l);
if(ssum-avg*(rr-l)) avg++;
if(avg>pre) return ;
if(u==-1&&tree[idd].max<=avg) u=avg,bg=l;
else if(u>=avg&&tree[idd].max<=avg)u=avg,bg=l;
// printf("~%d %d %d %lld %lld %lld\n",l,r,bg,u,ssum,pre);
if(r-l<=1) return ;
Down(idd);
long long mid=(l+r)/2;
if(tree[idd<<1].min*(rr-tree[idd<<1|1].l)>=tree[idd<<1|1].sum+num) Date(mid,r,rr,num,tree[idd<<1].min,idd<<1|1);
else {
ftt+=tree[idd<<1|1].sum;
Date(l,mid,rr,num,pre,idd<<1);
}
Up(idd);
}
void Update(long long l,long long r,long long rr,long long num,long long pre,long long idd){
if(tree[idd].l==l&&tree[idd].r==r){
Date(l,r,rr,num,pre,idd);
ftt+=tree[idd].sum;
return;
}
Down(idd);
long long mid=(tree[idd].l+tree[idd].r)/2;
if(mid>=r)
Update(l,r,rr,num,pre,idd<<1);
else if(mid<=l)
Update(l,r,rr,num,tree[idd<<1].min,idd<<1|1);
else{
Update(mid,r,rr,num,tree[idd<<1].min,idd<<1|1);
Update(l,mid,rr,num,pre,idd<<1);
}
Up(idd);
}
void Query(long long l,long long r,long long idd){
if(tree[idd].l==l&&tree[idd].r==r){
ssum+=tree[idd].sum;
return;
}
Down(idd);
long long mid=(tree[idd].l+tree[idd].r)/2;
if(mid>=r)
Query(l,r,idd<<1);
else if(mid<=l)
Query(l,r,idd<<1|1);
else{
Query(l,mid,idd<<1);
Query(mid,r,idd<<1|1);
}
Up(idd);
}
void fugai(long long l,long long r,long long shu,long long idd){
if(tree[idd].l==l&&tree[idd].r==r){
tree[idd].max=tree[idd].min=shu;
tree[idd].sum=(r-l)*shu;
tree[idd].fg=1;
return;
}
Down(idd);
long long mid=(tree[idd].l+tree[idd].r)/2;
if(mid>=r)
fugai(l,r,shu,idd<<1);
else if(mid<=l)
fugai(l,r,shu,idd<<1|1);
else{
fugai(l,mid,shu,idd<<1);
fugai(mid,r,shu,idd<<1|1);
}
Up(idd);
}
void Print(long long l,long long r,long long idd){
if(r-l<=1) {
printf("%lld\n",tree[idd].sum);
return;
}
Down(idd);
long long mid=(r+l)/2;
Print(l,mid,idd<<1);
Print(mid,r,idd<<1|1);
Up(idd);
}
int main(){
oo=1LL*2000000*10000000+10;
scanf("%lld%lld",&n,&q);
Init(1,n+1,1);
for(long long i=1;i<=q;i++){
long long x;long long y;
scanf("%lld%lld",&x,&y);
u=-1;bg=-1;
ftt=0;
Update(1,x+1,x+1,y,oo,1);
ssum=0;
Query(bg,x+1,1);
long long num=(x+1)-bg;
long long sum=ssum+y;
long long avg=sum/num;
long long a1=sum-avg*num;
if(a1){
fugai(bg,bg+a1,avg+1,1);
}
fugai(bg+a1,x+1,avg,1);
// Print(1,n+1,1);
}
Print(1,n+1,1);
return 0;
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:128:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&n,&q);
^
./Main.cpp:132:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&x,&y);
^