Submission #3772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3772	2013-08-31T08:15:35 Z	cki86201	Evaluation (kriii1_E)	C++	0 / 1	0 ms	4336 KB

E

#include<stdio.h>
#include<algorithm>

const int M=1000000007;

struct node{
	long long add, tot, sum;
	node* left, *right;
	node(){ left = right = 0; add=tot=sum=0; }
};

struct segment{
	int s,e,y,su;
	bool operator<(const segment &l)const{
		return y<l.y;
	}
};

struct SegmentTree{
	node* root;
	int start, end;
	SegmentTree(){}
	SegmentTree(int start, int end):start(start),end(end){ root = new node(); }

	void DFS(node* n, int s, int e, int l, int r, int su) // s-e: node가 담당하는 구간, l-r: 갱신하려는 구간
	{
		int cnt=e-s+1;
		if(e < l || r < s ) return; // 구간이 겹치지 않는 경우 
		if(l <= s && e <= r){
			n->add += su;
			if(!n->left){
				n->sum=cnt*n->add;
				n->tot=((cnt*n->add)%M*n->add)%M;
				n->sum%=M;
				n->tot%=M;
			}
			else{
				n->sum=n->left->sum+n->right->sum+(cnt*n->add)%M;
				n->tot=n->left->tot+n->right->tot+(n->add*(2*n->sum-(cnt*n->add)%M))%M;
				n->sum%=M;
				n->tot%=M;
			}
			return;
		}
		// 나머지
		if( !n->left ) n->left = new node(), n->right = new node();
		int m = ( s + e ) / 2;
		DFS(n->left, s, m, l, r, su);
		DFS(n->right, m+1, e, l, r, su);
		n->sum=n->left->sum+n->right->sum+(cnt*n->add)%M;
		n->tot=n->left->tot+n->right->tot+(n->add*(2*n->sum-(cnt*n->add)%M))%M;
		n->sum%=M;
		n->tot%=M;
	}

	void insert(int left, int right,int su)
	{
		DFS(root, start, end, left, right, su);
	}
	int read()
	{
		return root ->tot;
	}
}Tree=SegmentTree(0,1000000500);

segment data[200005];
int n;

int main()
{
	int i,a,b,c,d,e;
	long long ans=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
		data[2*i].s=a; data[2*i].e=c; data[2*i].su=e; data[2*i].y=b;
		data[2*i+1].s=a; data[2*i+1].e=c; data[2*i+1].su=-e; data[2*i+1].y=d+1;
	}
	std::sort(data,data+2*n);
	Tree.insert(data[0].s,data[0].e,data[0].su);
	for(int i=1;i<2*n;i++){
		ans+=Tree.read()*(data[i].y-data[i-1].y);
		Tree.insert(data[i].s,data[i].e,data[i].su);
	}
	printf("%lld",ans);
}

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	-