Submission #19087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19087	2016-02-18T05:50:21 Z	cki86201	Evaluation (kriii1_E)	C++	0 / 1	397 ms	65536 KB

E

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

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	4844 KB	Output is correct
2	Correct	0 ms	4844 KB	Output is correct
3	Correct	0 ms	4844 KB	Output is correct
4	Correct	0 ms	4844 KB	Output is correct
5	Correct	0 ms	4976 KB	Output is correct
6	Correct	0 ms	4844 KB	Output is correct
7	Correct	0 ms	4844 KB	Output is correct
8	Correct	3 ms	4976 KB	Output is correct
9	Correct	4 ms	5504 KB	Output is correct
10	Correct	7 ms	6296 KB	Output is correct
11	Correct	10 ms	4844 KB	Output is correct
12	Correct	21 ms	4844 KB	Output is correct
13	Correct	21 ms	5240 KB	Output is correct
14	Correct	43 ms	9332 KB	Output is correct
15	Correct	54 ms	17780 KB	Output is correct
16	Correct	170 ms	4844 KB	Output is correct
17	Correct	189 ms	4844 KB	Output is correct
18	Correct	222 ms	5372 KB	Output is correct
19	Correct	397 ms	23720 KB	Output is correct
20	Memory limit exceeded	327 ms	65536 KB	Memory limit exceeded