Submission #5127

#	Time	Username	Problem	Language	Result	Execution time	Memory
5127		ainta	Evaluation (kriii1_E)	C++98	1 / 1	280 ms	14776 KiB

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