Submission #4059

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4059	2013-08-31T16:21:52 Z	wookayin	Evaluation (kriii1_E)	C++	1 / 1	656 ms	27820 KB

E

#pragma warning(disable:4996)

#include <cassert>
#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;
int weight[200001 * 2];	// 좌표축소된 y 한칸의 길이.

struct node {
	int common_value;	// lazy propagation
	int length;

	int sum;
	int sum_sq;

	node() {
		common_value = length = 0;
		sum = sum_sq = 0;
	}
};
node tree[524387 * 2];


void build_tree(int x = 0, int y = 262143, int ti = 1) {

	node &t = tree[ti];
	if(x == y) {
		t.length = weight[x];
		return;
	}
	int mid = (x+y) / 2;
	build_tree(x, mid, ti * 2);
	build_tree(mid + 1, y, ti * 2 + 1);
	t.length = tree[ti*2].length + tree[ti*2+1].length;
	t.length %= MOD;
}

inline long long _(long long x) {
	return ((x % MOD) + MOD) % MOD;
}

void update(int l, int r, int delta, int x = 0, int y = 262143, int ti = 1) {
	node &t = tree[ti];

	if(l <= x && y <= r) {
		// t의 구간이 [l, r]에 포함된다.
		t.common_value += delta;
		t.sum_sq = _(0LL + t.sum_sq + (2LL * t.sum * delta) + _(1LL * delta * delta) * t.length);
		t.sum = _(0LL + t.sum + 1LL * delta * t.length);
		return;
	}

	int mid = (x + y) / 2;
	if(l <= mid) update(l, r, delta, x, mid, ti * 2);
	if(mid < r) update(l, r, delta, mid + 1, y, ti * 2 + 1);

	node &L = tree[ti * 2], &R = tree[ti * 2 + 1];
	t.sum = _(0LL + L.sum + R.sum + _(1LL * t.length * t.common_value));
	t.sum_sq = _(0LL + _(L.sum_sq + R.sum_sq) + 2LL * _(_(L.sum + R.sum) * (t.common_value)) + _(1LL * t.common_value * t.common_value) * t.length);
}

long long query() {
	long long t = tree[1].sum_sq % MOD;
	return t;
}

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

	build_tree();

	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 - 1, events[i].flag);
#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", tree[1].sum_sq, tree[1].sum);
#endif
		}

		last_x = x;
	}

	return ans % MOD;
}

void compactify() {
	// y의 범위들을 좌표 축소.
	vector<int> ys;
	
	for(unsigned i = 0; i < events.size(); ++ i) {
		Event &e = events[i];
		ys.push_back(e.y1);
		ys.push_back(e.y2);
	}
	sort(ys.begin(), ys.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());

	for(int i = 0; i < (int)ys.size() - 1; ++ i) {
		weight[i] = ys[i+1] - ys[i];
	}
	for(unsigned i = 0; i < events.size(); ++ i) {
		Event &e = events[i];
		e.y1 = distance(ys.begin(), lower_bound(ys.begin(), ys.end(), e.y1));
		e.y2 = distance(ys.begin(), lower_bound(ys.begin(), ys.end(), e.y2));
	}
}

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

	scanf("%d", &n);
	
	if(!(1 <= n && n <= 100000)) while(true);

	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+1, +p) );
		events.push_back( Event(c+1, b, d+1, -p) );
	}
	sort(events.begin(), events.end());

	compactify();
	cout << go() << endl;

	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	19628 KB	Output is correct
2	Correct	4 ms	19628 KB	Output is correct
3	Correct	4 ms	19628 KB	Output is correct
4	Correct	4 ms	19628 KB	Output is correct
5	Correct	8 ms	19628 KB	Output is correct
6	Correct	4 ms	19628 KB	Output is correct
7	Correct	8 ms	19628 KB	Output is correct
8	Correct	8 ms	19628 KB	Output is correct
9	Correct	4 ms	19628 KB	Output is correct
10	Correct	8 ms	19628 KB	Output is correct
11	Correct	44 ms	20652 KB	Output is correct
12	Correct	48 ms	20652 KB	Output is correct
13	Correct	52 ms	20652 KB	Output is correct
14	Correct	64 ms	20652 KB	Output is correct
15	Correct	52 ms	20652 KB	Output is correct
16	Correct	352 ms	27820 KB	Output is correct
17	Correct	392 ms	27820 KB	Output is correct
18	Correct	480 ms	27820 KB	Output is correct
19	Correct	640 ms	27820 KB	Output is correct
20	Correct	656 ms	27820 KB	Output is correct