Submission #3810

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3810	2013-08-31T08:28:55 Z	wookayin	Evaluation (kriii1_E)	C++	0 / 1	0 ms	1676 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;

struct node {
	node *L, *R;

	int x, y;	// 왼쪽, 오른쪽 좌표
	int 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 int length() const { return y - x + 1; }
	node(int x, int 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);

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

void update(unsigned l, unsigned r, int val, node *t = root) {
	if(l <= t->x && t->y <= r) {
		// 구간이 포함됨.
		t->common_value += val;
		t->sum_square += 2 * t->sum * val + val * val * t->length();
		t->sum_square %= MOD;
		t->sum += val * t->length();
		t->sum %= MOD;
		return;
	}
	int 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());
	}

	// 업데이트
	int affected_length = getLength(max<unsigned>(l, t->x), min<unsigned>(r, t->y));

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

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

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

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) {
//			fprintf(stderr, "<sum> s = %lld, dx = %d \n", query(), x-last_x);
			ans += query() % MOD * (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) {
//			fprintf(stderr, "x=%lld, update [%d, %d] with  %d", x, events[i].y1, events[i].y2, events[i].flag);
			update(events[i].y1, events[i].y2, events[i].flag, root);
//			fprintf(stderr, " : %lld <sum=%lld>\n", root->sum_square, root->sum);
		}

		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;
	delete root;

	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	1676 KB	Output isn't correct
2	Halted	0 ms	0 KB	-