Submission #3921

#	Time	Username	Problem	Language	Result	Execution time	Memory
3921		wookayin	Evaluation (kriii1_E)	C++98	0 / 1	800 ms	65536 KiB

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;

//#define DEBUG 1

struct node {
	node *L, *R;

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

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

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

		t->sum += val * t->length();
		t->sum %= MOD;
		return;
	}

	long long 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());
	}

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

	// 업데이트
	t->sum_square = _(t->getLeft()->sum_square + t->getRight()->sum_square)
		+ _(2 * _((t->getLeft()->sum + t->getRight()->sum) * t->common_value)) + _(_(t->common_value * t->common_value) * t->length());
	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 / 1