Submission #3860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3860	2013-08-31T08:54:14 Z	cki86201	Evaluation (kriii1_E)	C++	0 / 1	8 ms	7376 KB

E

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

const int M=1000000007;

struct node{
	int 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: 갱신하려는 구간
	{
		long long 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)%M;
				n->tot=(((cnt*n->add)%M)*n->add)%M;
			}
			else{
				n->sum=((long long)n->left->sum+n->right->sum+(cnt*n->add)%M)%M;
				n->tot=((long long)n->left->tot+n->right->tot+((long long)n->add*((2ll*n->sum-(cnt*n->add)%M)%M)%M)%M)%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=((long long)n->left->sum+n->right->sum+(cnt*n->add)%M)%M;
		n->tot=((long long)n->left->tot+n->right->tot+((long long)n->add*((2ll*n->sum-(cnt*n->add)%M)%M)%M)%M)%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	4340 KB	Output is correct
2	Correct	0 ms	4340 KB	Output is correct
3	Correct	0 ms	4340 KB	Output is correct
4	Correct	0 ms	4472 KB	Output is correct
5	Correct	0 ms	4604 KB	Output is correct
6	Correct	0 ms	4340 KB	Output is correct
7	Correct	4 ms	4340 KB	Output is correct
8	Correct	4 ms	4604 KB	Output is correct
9	Correct	0 ms	5660 KB	Output is correct
10	Incorrect	8 ms	7376 KB	Output isn't correct
11	Halted	0 ms	0 KB	-