답안 #5127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5127	2014-02-10T08:51:52 Z	ainta	Evaluation (kriii1_E)	C++	1 / 1	280 ms	14776 KB

E

#include<stdio.h>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, Y[200010];
long long SS, Mod = 1000000007, Sum, res;
struct YY{
	int y, num;
	bool operator <(const YY &p)const{
		return y < p.y;
	}
}p[201000];
struct Seg{
	int x, y1, y2, p;
	bool operator <(const Seg &p)const{
		return x < p.x;
	}
}w[201000];
struct SegTree{
	int K;
	long long S;
}IT[SZ * 2 + 1];
void spread(int node, long long K, int b, int e, int m){
	int c1 = node * 2, c2 = node * 2 + 1;
	IT[c1].K += K, IT[c2].K += K;
	IT[c1].S += K*(Y[m + 1] - Y[b]);
	IT[c2].S += K*(Y[e + 1] - Y[m + 1]);
	IT[node].K = 0;
}
void Add(int node, int b, int e, int s, int l, long long x){
	if (b == s && e == l){
		Sum += IT[node].S;
		IT[node].K += x;
		IT[node].S += x*(Y[e + 1] - Y[b]);
		return;
	}
	int m = (b + e) >> 1;
	if (IT[node].K)spread(node, IT[node].K, b, e, m);
	if (s <= m)Add(node * 2, b, m, s, min(l, m), x);
	if (l > m)Add(node * 2 + 1, m + 1, e, max(m + 1, s), l, x);
	IT[node].S = IT[node * 2].S + IT[node * 2 + 1].S;
}
int main(){
	int i, y1, y2, c = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d%d%d%d%d", &w[i * 2].x, &p[i * 2].y, &w[i * 2 + 1].x, &p[i * 2 + 1].y, &w[i * 2].p);
		w[i * 2 + 1].x++, w[i * 2 + 1].p = -w[i * 2].p;
		p[i * 2 + 1].y++;
		p[i * 2].num = i * 2, p[i * 2 + 1].num = i * 2 + 1;
	}
	sort(p, p + 2 * n);
	for (i = 0; i < 2 * n; i++){
		if (!i || p[i].y != p[i - 1].y)Y[++c] = p[i].y;
		if (p[i].num & 1)w[p[i].num].y2 = w[p[i].num ^ 1].y2 = c;
		else w[p[i].num].y1 = w[p[i].num ^ 1].y1 = c;
	}
	sort(w, w + 2 * n);
	for (i = 0; i < 2 * n; i++){
		Sum = 0;
		Add(1, 1, SZ, w[i].y1, w[i].y2 - 1, w[i].p);
		Sum %= Mod;
		SS = SS + Sum * 2 * w[i].p + (long long)(Y[w[i].y2] - Y[w[i].y1])*w[i].p*w[i].p;
		if (SS < 0)SS += (-SS) / Mod*Mod + Mod;
		SS %= Mod;
		if (w[i].x != w[i + 1].x)res = (res + SS*(w[i + 1].x - w[i].x)) % Mod;
	}
	printf("%lld\n", res);
}

Subtask #1

1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	14776 KB	Output is correct
2	Correct	0 ms	14776 KB	Output is correct
3	Correct	0 ms	14776 KB	Output is correct
4	Correct	0 ms	14776 KB	Output is correct
5	Correct	0 ms	14776 KB	Output is correct
6	Correct	0 ms	14776 KB	Output is correct
7	Correct	0 ms	14776 KB	Output is correct
8	Correct	0 ms	14776 KB	Output is correct
9	Correct	0 ms	14776 KB	Output is correct
10	Correct	0 ms	14776 KB	Output is correct
11	Correct	12 ms	14776 KB	Output is correct
12	Correct	12 ms	14776 KB	Output is correct
13	Correct	20 ms	14776 KB	Output is correct
14	Correct	24 ms	14776 KB	Output is correct
15	Correct	24 ms	14776 KB	Output is correct
16	Correct	136 ms	14776 KB	Output is correct
17	Correct	164 ms	14776 KB	Output is correct
18	Correct	188 ms	14776 KB	Output is correct
19	Correct	272 ms	14776 KB	Output is correct
20	Correct	280 ms	14776 KB	Output is correct