답안 #3939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3939	2013-08-31T09:31:40 Z	wookayin	Evaluation (kriii1_E)	C++	0 / 1	740 ms	65536 KB

E

#pragma warning(disable:4996)
#pragma pack(1)

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


struct node {
	node *L, *R;

	int common_value;	// lazy propagated value
	long long sum;
	long long sum_square;

	node *getLeft() {
		if(L == 0) L = new node();
		return L;
	}
	node *getRight() {
		if(R == 0) R = new node();
		return R;
	}
	inline int leftSum() { return L == 0 ? 0 : L->sum; }
	inline int rightSum() { return R == 0 ? 0 : R->sum; }
	inline int leftSumSquare() { return L == 0 ? 0 : L->sum_square; }
	inline int rightSumSquare() { return R == 0 ? 0 : R->sum_square; }

	node() {
		L = R = 0;
		common_value = 0;
		sum = 0;
		sum_square = 0;
	}
	~node() {
		if(L) delete L;
		if(R) delete R;
	}
};

node *root = new node();

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, unsigned x = 0, unsigned y = 1073741823) {
	int len = y-x+1;
	if(l <= x && y <= r) {
		// 구간이 포함됨.
		t->common_value += val;
		t->common_value %= MOD;

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

		t->sum += val * len;
		t->sum %= MOD;
		return;
	}

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

	t->sum = _(t->leftSum() + t->rightSum()) + _(len * (long long)t->common_value);
	t->sum %= MOD;

	// 업데이트
	t->sum_square = _(t->leftSumSquare() + t->rightSumSquare())
		+ _(2 * _((t->leftSum() + t->rightSum()) * (long long)t->common_value)) 
		+ _(_((long long)t->common_value * t->common_value) * len);
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1676 KB	Output is correct
2	Correct	0 ms	1676 KB	Output is correct
3	Correct	0 ms	1676 KB	Output is correct
4	Correct	0 ms	1808 KB	Output is correct
5	Correct	0 ms	1940 KB	Output is correct
6	Correct	0 ms	1676 KB	Output is correct
7	Correct	4 ms	1676 KB	Output is correct
8	Correct	4 ms	1940 KB	Output is correct
9	Correct	4 ms	2732 KB	Output is correct
10	Correct	8 ms	3920 KB	Output is correct
11	Correct	28 ms	2448 KB	Output is correct
12	Correct	36 ms	2448 KB	Output is correct
13	Correct	40 ms	2852 KB	Output is correct
14	Correct	68 ms	8792 KB	Output is correct
15	Correct	120 ms	21596 KB	Output is correct
16	Correct	308 ms	7824 KB	Output is correct
17	Correct	336 ms	7824 KB	Output is correct
18	Correct	400 ms	7824 KB	Output is correct
19	Correct	740 ms	33760 KB	Output is correct
20	Memory limit exceeded	268 ms	65536 KB	Memory limit exceeded