Submission #4643

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4643	2013-11-14T18:18:36 Z	cki86201	Evaluation (kriii1_E)	C++	0 / 1	484 ms	65536 KB

E

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll M = 1e9+7;

struct node{
	node(){x=c=0,L=0LL,left=right=NULL;}
	int x,c;
	long long L;
	node *left,*right;
}*tree;

ll update(node *R,int l,int r,int s,int e,int u){
	if(l<=s&&e<=r){
		R->c+=u;
		ll tmp = R->L;
		R->L += (ll)(e-s+1)*u;
		R->L %= M;
		return tmp;
	}
	int m = (s+e)>>1;
	ll d=0;
	if(l<=m){
		if(!R->left)R->left = new node();
		d += update(R->left,l,r,s,m,u);
	}
	if(r>m){
		if(!R->right)R->right = new node();
		d += update(R->right,l,r,m+1,e,u);
	}
	R->L += (ll)(min(e,r)-max(l,s)+1)*u;
	R->L %= M;
	return (d+(ll)R->c*(min(e,r)-max(l,s)+1))%M;
}

int in[200020][2],N;
int p[200020],ord[200020];
ll ans,now;
bool comp(const int &a,const int &b){return in[a][0]<in[b][0];}

int main()
{
	tree = new node();
	scanf("%d",&N);
	int i;
	for(i=0;i<N;i++){
		scanf("%d%d%d%d%d",in[2*i],in[2*i]+1,in[2*i+1],in[2*i+1]+1,p+2*i);
		p[2*i+1]=p[2*i];
		in[2*i+1][0]++,in[2*i+1][1]++;
		ord[2*i]=2*i,ord[2*i+1]=2*i+1;
	}
	sort(ord,ord+2*N,comp);
	for(i=0;i<2*N;i++){
		int x = ord[i]/2, u = p[ord[i]] * ((ord[i]&1)?-1:1);
		int a = in[2*x][1], b = in[2*x+1][1]-1;
		if(i)ans += now*(in[ord[i]][0]-in[ord[i-1]][0]);
		now += (ll)(b-a+1)*u*u;
		int y = (u+M)%M;
		now += 2*y*update(tree,a,b,1,1e9,u);
		now %= M;
	}
	printf("%d",int(ans%M));
}

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	5392 KB	Output is correct
10	Correct	4 ms	6580 KB	Output is correct
11	Correct	12 ms	4336 KB	Output is correct
12	Correct	20 ms	4336 KB	Output is correct
13	Correct	20 ms	4996 KB	Output is correct
14	Correct	44 ms	11068 KB	Output is correct
15	Correct	68 ms	23872 KB	Output is correct
16	Correct	176 ms	4336 KB	Output is correct
17	Correct	196 ms	4336 KB	Output is correct
18	Correct	252 ms	5128 KB	Output is correct
19	Correct	484 ms	32716 KB	Output is correct
20	Memory limit exceeded	256 ms	65536 KB	Memory limit exceeded