Submission #4041

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4041	2013-08-31T15:22:44 Z	wookayin	Evaluation (kriii1_E)	C++	0 / 1	40 ms	19868 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;
int weight[100001 * 2];	// 좌표축소된 y 한칸의 길이.

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

	long long sum;
	long long sum_sq;

	node() {
		common_value = length = 0;
		sum = sum_sq = 0;
	}
};
node tree[131072 * 4 + 10];

void build_tree(int x = 0, int y = 131072, 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;
}

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

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

	if(l <= x && y <= r) {
		// t의 구간이 [l, r]에 포함된다.
		t.common_value += delta;
		t.sum_sq += _(2 * t.sum * delta) + _(1LL * delta * delta) * t.length;
		t.sum_sq %= MOD;
		t.sum += (long long)delta * t.length;
		t.sum %= MOD;
		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 = L.sum + R.sum + _(t.length * t.common_value);
	t.sum %= MOD;
	t.sum_sq = _(L.sum_sq + R.sum_sq) + 2LL * _(L.sum + R.sum) * (t.common_value) + _(t.common_value * t.common_value) * t.length;
	t.sum_sq %= MOD;
}

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

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;
}

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() {
#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+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

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	18844 KB	Output is correct
2	Correct	0 ms	18844 KB	Output is correct
3	Correct	0 ms	18844 KB	Output is correct
4	Correct	0 ms	18844 KB	Output is correct
5	Correct	4 ms	18844 KB	Output is correct
6	Correct	4 ms	18844 KB	Output is correct
7	Correct	8 ms	18844 KB	Output is correct
8	Correct	4 ms	18844 KB	Output is correct
9	Correct	4 ms	18844 KB	Output is correct
10	Correct	4 ms	18844 KB	Output is correct
11	Correct	20 ms	19868 KB	Output is correct
12	Correct	32 ms	19868 KB	Output is correct
13	Correct	36 ms	19868 KB	Output is correct
14	Incorrect	40 ms	19868 KB	Output isn't correct
15	Halted	0 ms	0 KB	-