제출 #4012

#제출 시각아이디문제언어결과실행 시간메모리
4012wookayinEvaluation (kriii1_E)C++98
0 / 1
88 ms65536 KiB
#pragma warning(disable:4996) #pragma pack(1) #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 { int L; int common_value; // lazy propagated value int sum; int sum_square; node &getLeft(); node &getRight(); node() { L = -1; common_value = 0; sum = 0; sum_square = 0; } inline int leftSum(); inline int rightSum(); inline int leftSumSquare(); inline int rightSumSquare(); }; node POOL[3900000]; int POOL_SZ = 0; node root; node & node::getLeft() { if(L == -1) L = POOL_SZ++; POOL_SZ ++; return POOL[L]; } node & node::getRight() { if(L == -1) L = POOL_SZ++; POOL_SZ ++; return POOL[L+1]; } inline int node::leftSum() { return L == -1 ? 0 : POOL[L].sum; } inline int node::rightSum() { return L == -1 ? 0 : POOL[L+1].sum; } inline int node::leftSumSquare() { return L == -1 ? 0 : POOL[L].sum_square; } inline int node::rightSumSquare() { return L == -1 ? 0 : POOL[L+1].sum_square; } long long getLength(long long l, long long r) { if(l < r) return r - l + 1; return 0; } inline long long _(long long v) { return v % MOD; } void update(long long l, long long r, long long val, node &t = root, unsigned x = 0, unsigned y = 1073741823) { int len = y-x+1; if(l <= x && y <= r) { // 구간이 포함됨. t.common_value += val; t.common_value %= MOD; t.sum_square += _(2LL * t.sum * val); t.sum_square %= MOD; t.sum_square += _(_(val * val) * len); t.sum_square %= MOD; t.sum += _(val * len); t.sum %= MOD; return; } unsigned mid = (x + y) / 2; // [x, mid] if(l <= mid) { // 왼쪽구간에 겹침ㄴ update(l, r, val, t.getLeft(), x, mid); } if(mid < r) { // 오른쪽 구간에 겹침 update(l, r, val, t.getRight(), mid + 1, y); } t.sum = _((long long)t.leftSum() + t.rightSum()) + _(len * (long long)t.common_value); t.sum %= MOD; // 업데이트 t.sum_square = _((long long)t.leftSumSquare() + t.rightSumSquare()); t.sum_square %= MOD; t.sum_square += _(2LL * _((t.leftSum() + t.rightSum()) * (long long)t.common_value)) ; t.sum_square %= MOD; t.sum_square += _(_((long long)t.common_value * t.common_value) * (long long)len); t.sum_square %= MOD; } long long query(node &t = root) { return t.sum_square % MOD; } 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) { #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, events[i].flag, root); #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", root.sum_square, root.sum); #endif } 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; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...