Submission #19088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19088	2016-02-18T05:55:56 Z	cki86201	Evaluation (kriii1_E)	C++	0 / 1	383 ms	65536 KB

E

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

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

const int MOD = 1e9 + 7;

struct line{
  line(){}
  line(int x,int y1,int y2,int v):x(x),y1(y1),y2(y2),v(v){}
	int x, y1, y2, v;
	bool operator<(const line &l)const{
		return x < l.x;
	}
}L[200010];

struct node{
	node(){x = u = 0, right = left = NULL;}
	int x, u;
	node *right, *left;
}*root;

int update(node *rt, int s, int d, int l, int r, int v){
	if(l <= s && d <= r){
		rt->u = (rt->u + v + MOD) % MOD;
		int tmp = rt->x;
		rt->x = (rt->x + (ll)(d-s+1) * v) % MOD;
		if(rt->x < 0)rt->x += MOD;
		return tmp;
	}
	int m = (s+d)>>1, res = 0;
	if(l<=m){
		if(!rt->left)rt->left = new node();
		res += update(rt->left, s, m, l, r, v);
	}
	if(m<r){
		if(!rt->right)rt->right = new node();
		res += update(rt->right, m+1, d, l, r, v);
	}
	rt->x = (rt->x + (ll)(min(d, r) - max(s, l) + 1) * v) % MOD;
	if(rt->x < 0)rt->x += MOD;
	res = (res + (ll)(min(d, r) - max(s, l) + 1) * rt->u) % MOD;
	return res;
}

int main(){
	int n; scanf("%d", &n);
	rep(i, n){
		int a, b, c, d, p;
		scanf("%d%d%d%d%d", &a, &b, &c, &d, &p);
		L[i+i] = line(a, b, d, p);
		L[i+i+1] = line(c+1, b, d, -p);
	}
	sort(L, L+n+n);
	root = new node();
	ll ans = 0;
	ll now = 0;
	for(int i=0;i<n+n;i++){
		if(i != 0){
			ans += now * (L[i].x - L[i-1].x), ans %= MOD;
		}
		now += (ll)(L[i].y2 - L[i].y1 + 1) * L[i].v * L[i].v;
		now += 2LL * L[i].v * update(root, 1, 1e9, L[i].y1, L[i].y2, L[i].v);
		now %= MOD;
		if(now < 0)now += MOD;
	}
	printf("%lld", ans);
	return 0;
}

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	4336 KB	Output is correct
5	Correct	0 ms	4468 KB	Output is correct
6	Correct	2 ms	4336 KB	Output is correct
7	Correct	0 ms	4336 KB	Output is correct
8	Correct	3 ms	4468 KB	Output is correct
9	Correct	4 ms	4996 KB	Output is correct
10	Correct	6 ms	5788 KB	Output is correct
11	Correct	17 ms	4336 KB	Output is correct
12	Correct	22 ms	4336 KB	Output is correct
13	Correct	25 ms	4732 KB	Output is correct
14	Correct	37 ms	8824 KB	Output is correct
15	Correct	59 ms	17272 KB	Output is correct
16	Correct	165 ms	4336 KB	Output is correct
17	Correct	201 ms	4336 KB	Output is correct
18	Correct	221 ms	4864 KB	Output is correct
19	Correct	383 ms	23212 KB	Output is correct
20	Memory limit exceeded	311 ms	65536 KB	Memory limit exceeded