# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
3824 | wookayin | Evaluation (kriii1_E) | C++98 | 0 ms | 1676 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;
struct node {
node *L, *R;
int x, y; // 왼쪽, 오른쪽 좌표
int common_value; // lazy propagated value
long long sum;
long long sum_square;
node *getLeft() {
if(L == 0) L = new node(x, (x+y)/2);
return L;
}
node *getRight() {
if(R == 0) R = new node((x+y)/2 + 1, y);
return R;
}
inline int length() const { return y - x + 1; }
node(int x, int y) : x(x), y(y) {
L = R = 0;
common_value = 0;
sum = 0;
sum_square = 0;
}
~node() {
if(L) delete L;
if(R) delete R;
}
};
node *root = new node(0, 1073741823);
int getLength(int l, int r) {
if(l < r) return r - l + 1;
return 0;
}
inline long long _(long long v) {
return v % MOD;
}
void update(int l, int r, int val, node *t = root) {
if(l <= t->x && t->y <= r) {
// 구간이 포함됨.
t->common_value += val;
t->sum_square += _(2 * t->sum * val) + _(val * val * t->length());
t->sum_square %= MOD;
t->sum += val * t->length();
t->sum %= MOD;
return;
}
int mid = (t->x + t->y) / 2;
// [x, mid]
if(l <= mid) { // 왼쪽구간에 겹침ㄴ
update(l, r, val, t->getLeft());
}
if(mid < r) { // 오른쪽 구간에 겹침
update(l, r, val, t->getRight());
}
// 업데이트
t->sum_square = _(t->getLeft()->sum_square + t->getRight()->sum_square)
+ _(2 * _(t->sum * t->common_value)) + _(_(t->common_value * t->common_value) * t->length());
t->sum_square %= MOD;
t->sum = _(t->getLeft()->sum + t->getRight()->sum) + _(t->length() * t->common_value);
t->sum %= MOD;
}
long long query(node *t = root) {
return t->sum_square;
}
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) {
// fprintf(stderr, "<sum> s = %lld, dx = %d \n", query(), x-last_x);
ans += query() % MOD * (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) {
// fprintf(stderr, "x=%lld, update [%d, %d] with %d", x, events[i].y1, events[i].y2, events[i].flag);
update(events[i].y1, events[i].y2, events[i].flag, root);
// fprintf(stderr, " : %lld <sum=%lld>\n", root->sum_square, root->sum);
}
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;
delete root;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |