Submission #3115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3115	2013-08-25T11:09:39 Z	ainta	Evaluation (kriii1_E)	C++	0 / 1	496 ms	65536 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+=p,node->c2->p+=p;
}
void make_child(SegTree *node){
	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){
		return (long long)node->p*(l-s+1);
	}
	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);
	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,1,1000000000,Y[i].y1,Y[i].y2)%Mod*T*2LL;
		S%=Mod;
		Ins(root,1,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	Correct	0 ms	4336 KB	Output is correct
2	Correct	0 ms	4336 KB	Output is correct
3	Correct	0 ms	4336 KB	Output is correct
4	Correct	0 ms	4468 KB	Output is correct
5	Correct	0 ms	4600 KB	Output is correct
6	Correct	0 ms	4336 KB	Output is correct
7	Correct	0 ms	4336 KB	Output is correct
8	Correct	0 ms	4600 KB	Output is correct
9	Correct	4 ms	5656 KB	Output is correct
10	Correct	8 ms	7372 KB	Output is correct
11	Correct	20 ms	4336 KB	Output is correct
12	Correct	24 ms	4336 KB	Output is correct
13	Correct	28 ms	5128 KB	Output is correct
14	Correct	40 ms	13180 KB	Output is correct
15	Correct	76 ms	30208 KB	Output is correct
16	Correct	200 ms	4336 KB	Output is correct
17	Correct	232 ms	4336 KB	Output is correct
18	Correct	264 ms	5260 KB	Output is correct
19	Correct	496 ms	40900 KB	Output is correct
20	Memory limit exceeded	196 ms	65536 KB	Memory limit exceeded