Submission #1227889


Source Code Expand

#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;
}

Submission Info

Submission Time
Task F - Sushi
User yingpingan
Language C++14 (Clang 3.8.0)
Score 0
Code Size 3672 Byte
Status CE

Compile Error

./Main.cpp:1:9: fatal error: 'bits/stdc++.h' file not found
#include<bits/stdc++.h>
        ^
1 error generated.