Submission #3939

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

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 / 1