답안 #4004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4004	2013-08-31T09:56:42 Z	wookayin	Evaluation (kriii1_E)	C++	0 / 1	404 ms	62512 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 {
	int L;

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

	node &getLeft();
	node &getRight();

	node() {
		L = -1;
		common_value = 0;
		sum = 0;
		sum_square = 0;
	}

	inline int leftSum();
	inline int rightSum();
	inline int leftSumSquare();
	inline int rightSumSquare();
};

node POOL[3500000];
int POOL_SZ = 0;

node root;

node & node::getLeft() {
	if(L == -1) L = POOL_SZ++; POOL_SZ ++;
	return POOL[L];
}
node & node::getRight() {
	if(L == -1) L = POOL_SZ++; POOL_SZ ++;
	return POOL[L+1];
}
inline int node::leftSum() { return L == -1 ? 0 : POOL[L].sum; }
inline int node::rightSum() { return L == -1 ? 0 : POOL[L+1].sum; }
inline int node::leftSumSquare() { return L == -1 ? 0 : POOL[L].sum_square; }
inline int node::rightSumSquare() { return L == -1 ? 0 : POOL[L+1].sum_square; }

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 += _(2LL * t.sum * val);
		t.sum_square %= MOD;
		t.sum_square += _(_(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 = _((long long)t.leftSum() + t.rightSum()) + _(len * (long long)t.common_value);
	t.sum %= MOD;

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

	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;

	return 0;
}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	56364 KB	Output is correct
2	Correct	8 ms	56364 KB	Output is correct
3	Correct	20 ms	56364 KB	Output is correct
4	Correct	8 ms	56364 KB	Output is correct
5	Correct	0 ms	56364 KB	Output is correct
6	Correct	12 ms	56364 KB	Output is correct
7	Correct	12 ms	56364 KB	Output is correct
8	Correct	12 ms	56364 KB	Output is correct
9	Correct	24 ms	56364 KB	Output is correct
10	Correct	20 ms	56364 KB	Output is correct
11	Correct	32 ms	57136 KB	Output is correct
12	Correct	52 ms	57136 KB	Output is correct
13	Correct	72 ms	57136 KB	Output is correct
14	Correct	72 ms	57136 KB	Output is correct
15	Correct	88 ms	57136 KB	Output is correct
16	Correct	380 ms	62512 KB	Output is correct
17	Correct	404 ms	62512 KB	Output is correct
18	Runtime error	248 ms	62512 KB	SIGSEGV Segmentation fault
19	Halted	0 ms	0 KB	-