Submission #3811

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3811	2013-08-31T08:29:13 Z	cki86201	Evaluation (kriii1_E)	C++	0 / 1	632 ms	65536 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))%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);
	}
	long long 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))%M;
		Tree.insert(data[i].s,data[i].e,data[i].su);
		ans%=M;
	}
	ans%=M;
	printf("%lld",ans);
}

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	4 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	56 ms	13180 KB	Output is correct
15	Correct	92 ms	30208 KB	Output is correct
16	Correct	220 ms	4336 KB	Output is correct
17	Correct	240 ms	4336 KB	Output is correct
18	Correct	296 ms	5260 KB	Output is correct
19	Correct	632 ms	40900 KB	Output is correct
20	Memory limit exceeded	248 ms	65536 KB	Memory limit exceeded