Submission #3921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3921	2013-08-31T09:22:40 Z	wookayin	Evaluation (kriii1_E)	C++	0 / 1	800 ms	65536 KB

E

#pragma warning(disable:4996)

#include <algorithm>
#include <functional>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

struct Event {
	int x;
	int y1, y2;
	int flag;
	Event(int x, int y1, int y2, int flag) : x(x), y1(y1), y2(y2), flag(flag) {}
};

bool operator < (const Event &A, const Event &B) {
	if(A.x != B.x) return A.x < B.x;
	else return A.flag < B.flag;	//-가 먼저
}

int n;
vector<Event> events;
const long long MOD = 1000000007;

//#define DEBUG 1

struct node {
	node *L, *R;

	long long x, y;	// 왼쪽, 오른쪽 좌표
	long long common_value;	// lazy propagated value
	long long sum;
	long long sum_square;

	node *getLeft() {
		if(L == 0) L = new node(x, (x+y)/2);
		return L;
	}
	node *getRight() {
		if(R == 0) R = new node((x+y)/2 + 1, y);
		return R;
	}
	inline long long length() const { return y - x + 1; }
	node(long long x, long long y) : x(x), y(y) {
		L = R = 0;
		common_value = 0;
		sum = 0;
		sum_square = 0;
	}
	~node() {
		if(L) delete L;
		if(R) delete R;
	}
};

node *root = new node(0, 1073741823);

long long getLength(long long l, long long r) {
	if(l < r) return r - l + 1;
	return 0;
}

inline long long _(long long v) {
	return v % MOD;
}

void update(long long l, long long r, long long val, node *t = root) {
	if(l <= t->x && t->y <= r) {
		// 구간이 포함됨.
		t->common_value += val;
		t->common_value %= MOD;

		t->sum_square += _(2 * t->sum * val) + _(_(val * val) * t->length());
		t->sum_square %= MOD;

		t->sum += val * t->length();
		t->sum %= MOD;
		return;
	}

	long long mid = (t->x + t->y) / 2;
	// [x, mid]
	if(l <= mid) { // 왼쪽구간에 겹침ㄴ
		update(l, r, val, t->getLeft());
	}
	if(mid < r) { // 오른쪽 구간에 겹침
		update(l, r, val, t->getRight());
	}

	t->sum = _(t->getLeft()->sum + t->getRight()->sum) + _(t->length() * t->common_value);
	t->sum %= MOD;

	// 업데이트
	t->sum_square = _(t->getLeft()->sum_square + t->getRight()->sum_square)
		+ _(2 * _((t->getLeft()->sum + t->getRight()->sum) * t->common_value)) + _(_(t->common_value * t->common_value) * t->length());
	t->sum_square %= MOD;
}

long long query(node *t = root) {
	return t->sum_square % MOD;
}

long long go() {
	long long last_x = -1;
	long long x;

	long long ans = 0;
	for(int i = 0; i < events.size(); ) {

		x = events[i].x;

		// 이 시점에서 면적을 더한다.
		if(last_x != -1) {
#ifdef DEBUG
			fprintf(stderr, "<sum> s = %lld, dx = %d \n", query(), x-last_x);
#endif
			ans += query() * (x - last_x);
			ans %= MOD;
		}

		int j;
		for(j = i; j < events.size() && events[j].x == events[i].x; ++ j);
		--j; // [i, j] 는 같은 x를 가짐

		for(; i <= j; ++ i) {
			update(events[i].y1, events[i].y2, events[i].flag, root);
#ifdef DEBUG
			fprintf(stderr, "x=%lld, update [%d, %d] with  %d", x, events[i].y1, events[i].y2, events[i].flag);
			fprintf(stderr, " : %lld <sum=%lld>\n", root->sum_square, root->sum);
#endif
		}

		last_x = x;
	}

	return ans;
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	scanf("%d", &n);
	for(int i = 0; i < n; ++ i) {
		int a,b,c,d,p;
		scanf("%d %d %d %d %d", &a, &b, &c, &d, &p);

		events.push_back( Event(a, b, d, +p) );
		events.push_back( Event(c+1, b, d, -p) );
	}
	sort(events.begin(), events.end());

	cout << go() << endl;
	delete root;

	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1680 KB	Output is correct
2	Correct	0 ms	1680 KB	Output is correct
3	Correct	0 ms	1680 KB	Output is correct
4	Correct	0 ms	1944 KB	Output is correct
5	Correct	0 ms	2076 KB	Output is correct
6	Correct	0 ms	1680 KB	Output is correct
7	Correct	4 ms	1812 KB	Output is correct
8	Correct	0 ms	2076 KB	Output is correct
9	Correct	4 ms	3528 KB	Output is correct
10	Correct	8 ms	5772 KB	Output is correct
11	Correct	28 ms	2452 KB	Output is correct
12	Correct	36 ms	2452 KB	Output is correct
13	Correct	44 ms	3252 KB	Output is correct
14	Correct	80 ms	13944 KB	Output is correct
15	Correct	140 ms	36648 KB	Output is correct
16	Correct	308 ms	7828 KB	Output is correct
17	Correct	332 ms	7828 KB	Output is correct
18	Correct	392 ms	7828 KB	Output is correct
19	Correct	800 ms	54092 KB	Output is correct
20	Memory limit exceeded	188 ms	65536 KB	Memory limit exceeded