# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
4044 | wookayin | Evaluation (kriii1_E) | C++98 | 4 ms | 18844 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma warning(disable:4996)
#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[100001 * 2]; // 좌표축소된 y 한칸의 길이.
struct node {
long long common_value; // lazy propagation
long long length;
long long sum;
long long sum_sq;
node() {
common_value = length = 0;
sum = sum_sq = 0;
}
};
node tree[(1<<18) * 2 + 100];
void build_tree(int x = 0, int y = (1<<18) - 1, 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;
}
inline long long _(long long x) {
return x % MOD;
}
void update(int l, int r, int delta, int x = 0, int y = (1<<18) - 1, int ti = 1) {
node &t = tree[ti];
if(l <= x && y <= r) {
// t의 구간이 [l, r]에 포함된다.
t.common_value += delta;
t.sum_sq += _(2 * t.sum * delta) + _(1LL * delta * delta) * t.length;
t.sum_sq %= MOD;
t.sum += delta * t.length;
t.sum %= MOD;
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 = L.sum + R.sum + _(t.length * t.common_value);
t.sum %= MOD;
t.sum_sq = _(L.sum_sq + R.sum_sq) + 2LL * _(_(L.sum + R.sum) * (t.common_value)) + _(t.common_value * t.common_value) * t.length;
t.sum_sq %= MOD;
}
long long query() {
return tree[1].sum_sq % MOD;
}
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;
}
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);
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |