Submission #3112

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3112	2013-08-25T10:28:13 Z	ainta	Evaluation (kriii1_E)	C++	0 / 1	0 ms	4336 KB

E

#include<stdio.h>
#include<algorithm>
using namespace std;
long long Mod=1000000007;
struct SegTree{
	SegTree(){
		S=0,p=0,c1=c2=NULL;
	}
	long long S;
	int p;
	SegTree *c1,*c2;
};
struct Seg{
	int x,y1,y2,p;
	bool operator <(const Seg &p)const{
		return x<p.x;
	}
}Y[200001];
int n,i,c;
long long S,T,Res;
void push(int x,int y1,int y2,int p){
	Y[c].x=x,Y[c].y1=y1,Y[c].y2=y2,Y[c].p=p;
	c++;
}
void spread(SegTree *node,int b,int e,int m){
	long long p=node->p;
	node->p=0;
	node->c1->S+=p*(m-b+1);
	node->c2->S+=p*(e-m);
	node->c1->p=node->c2->p=p;
}
void make_child(SegTree *node,long long k,int a,int b){
	node->c1=new SegTree();
	node->c2=new SegTree();
}
long long Sum(SegTree *node,int b,int e,int s,int l){
	if(b==s && e==l){
		return node->S;
	}
	int m=(b+e)>>1;
	if(node->c1==NULL)make_child(node,node->S/(e-b+1),m-b+1,e-m);
	if(node->p)spread(node,b,e,m);
	long long ss=0;
	if(m>=s){
		ss+=Sum(node->c1,b,m,s,min(m,l));
	}
	if(m+1<=l){
		ss+=Sum(node->c2,m+1,e,max(s,m+1),l);
	}
	return ss;
}
void Ins(SegTree *node,int b,int e,int s,int l,int p){
	if(b==s && e==l){
		node->S+=(long long)(e-b+1)*p;
		node->p+=p;
		return;
	}
	int m=(b+e)>>1;
	if(node->c1==NULL)make_child(node,node->S/(e-b+1),m-b+1,e-m);
	if(node->p)spread(node,b,e,m);
	if(m>=s){
		Ins(node->c1,b,m,s,min(m,l),p);
	}
	if(m+1<=l){
		Ins(node->c2,m+1,e,max(s,m+1),l,p);
	}
	node->S=node->c1->S+node->c2->S;
}
int main()
{
	int x1,y1,x2,y2,a;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&a);
		push(x1,y1,y2,a);
		push(x2+1,y1,y2,-a);
	}
	sort(Y,Y+c);
	SegTree *root=new SegTree();
	for(i=0;i<c;i++){
		S+=(long long)(Y[i].y2-Y[i].y1+1)*Y[i].p*Y[i].p;
		T=(Mod+Y[i].p)%Mod;
		S+=Sum(root,0,1000000000,Y[i].y1,Y[i].y2)%Mod*T*2LL;
		S%=Mod;
		Ins(root,0,1000000000,Y[i].y1,Y[i].y2,Y[i].p);
		if(i!=c-1 && Y[i].x!=Y[i+1].x){
			Res+=S*(Y[i+1].x-Y[i].x);
			Res%=Mod;
		}
	}
	printf("%lld\n",Res);
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	4336 KB	Output isn't correct
2	Halted	0 ms	0 KB	-