Submission #3974

#	Time	Username	Problem	Language	Result	Execution time	Memory
3974		wookayin	Evaluation (kriii1_E)	C++98	0 / 1	660 ms	54308 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 {
	int L, R;

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

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

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

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

node POOL[1700000];
int POOL_SZ = 0;

node root;

node & node::getLeft() {
	if(L == -1) L = POOL_SZ++;
	return POOL[L];
}
node & node::getRight() {
	if(R == -1) R = POOL_SZ++;
	return POOL[R];
}
inline int node::leftSum() { return L == -1 ? 0 : POOL[L].sum; }
inline int node::rightSum() { return R == -1 ? 0 : POOL[R].sum; }
inline int node::leftSumSquare() { return L == -1 ? 0 : POOL[L].sum_square; }
inline int node::rightSumSquare() { return R == -1 ? 0 : POOL[R].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 += _(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() {

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