Submission #4059

#	Time	Username	Problem	Language	Result	Execution time	Memory
4059		wookayin	Evaluation (kriii1_E)	C++98	1 / 1	656 ms	27820 KiB

E

#pragma warning(disable:4996)

#include <cassert>
#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;
int weight[200001 * 2];	// 좌표축소된 y 한칸의 길이.

struct node {
	int common_value;	// lazy propagation
	int length;

	int sum;
	int sum_sq;

	node() {
		common_value = length = 0;
		sum = sum_sq = 0;
	}
};
node tree[524387 * 2];


void build_tree(int x = 0, int y = 262143, int ti = 1) {

	node &t = tree[ti];
	if(x == y) {
		t.length = weight[x];
		return;
	}
	int mid = (x+y) / 2;
	build_tree(x, mid, ti * 2);
	build_tree(mid + 1, y, ti * 2 + 1);
	t.length = tree[ti*2].length + tree[ti*2+1].length;
	t.length %= MOD;
}

inline long long _(long long x) {
	return ((x % MOD) + MOD) % MOD;
}

void update(int l, int r, int delta, int x = 0, int y = 262143, int ti = 1) {
	node &t = tree[ti];

	if(l <= x && y <= r) {
		// t의 구간이 [l, r]에 포함된다.
		t.common_value += delta;
		t.sum_sq = _(0LL + t.sum_sq + (2LL * t.sum * delta) + _(1LL * delta * delta) * t.length);
		t.sum = _(0LL + t.sum + 1LL * delta * t.length);
		return;
	}

	int mid = (x + y) / 2;
	if(l <= mid) update(l, r, delta, x, mid, ti * 2);
	if(mid < r) update(l, r, delta, mid + 1, y, ti * 2 + 1);

	node &L = tree[ti * 2], &R = tree[ti * 2 + 1];
	t.sum = _(0LL + L.sum + R.sum + _(1LL * t.length * t.common_value));
	t.sum_sq = _(0LL + _(L.sum_sq + R.sum_sq) + 2LL * _(_(L.sum + R.sum) * (t.common_value)) + _(1LL * t.common_value * t.common_value) * t.length);
}

long long query() {
	long long t = tree[1].sum_sq % MOD;
	return t;
}

long long go() {
	long long last_x = -1;
	long long x;
	long long ans = 0;

	build_tree();

	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 - 1, events[i].flag);
#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", tree[1].sum_sq, tree[1].sum);
#endif
		}

		last_x = x;
	}

	return ans % MOD;
}

void compactify() {
	// y의 범위들을 좌표 축소.
	vector<int> ys;
	
	for(unsigned i = 0; i < events.size(); ++ i) {
		Event &e = events[i];
		ys.push_back(e.y1);
		ys.push_back(e.y2);
	}
	sort(ys.begin(), ys.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());

	for(int i = 0; i < (int)ys.size() - 1; ++ i) {
		weight[i] = ys[i+1] - ys[i];
	}
	for(unsigned i = 0; i < events.size(); ++ i) {
		Event &e = events[i];
		e.y1 = distance(ys.begin(), lower_bound(ys.begin(), ys.end(), e.y1));
		e.y2 = distance(ys.begin(), lower_bound(ys.begin(), ys.end(), e.y2));
	}
}

int main() {
#if 0
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	scanf("%d", &n);
	
	if(!(1 <= n && n <= 100000)) while(true);

	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+1, +p) );
		events.push_back( Event(c+1, b, d+1, -p) );
	}
	sort(events.begin(), events.end());

	compactify();
	cout << go() << endl;

	return 0;
}

• Subtask 1: 1 / 1