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