#include <iostream>
#include <cstdio>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
struct Node{
Node(){x=up=dn=v=0;}
Node(int _x, int _dn, int _up, int _v) {
x = _x; up = _up; dn = _dn, v = _v;
}
int x, up, dn, v;
bool operator<(const Node & A) const{
if( x == A.x ) return v < A.v;
return x < A.x;
}
} node[100000*2];
struct interval{
interval() {
cnt = sum = 0;
L = R = NULL;
}
ll cnt, sum;
interval *L, *R;
};
int N;
void insert(interval *it, int a, int b, int l, int r, int v) {
if( a <= l && r <= b ) (*it).cnt += v;
else {
int mid = (l+r)/2;
if( a <= mid ) {
if( (*it).L == NULL) (*it).L = new interval();
insert((*it).L, a, b, l, mid, v);
}
if( mid < b ) {
if( (*it).R == NULL) (*it).R = new interval();
insert((*it).R, a, b, mid+1, r, v);
}
}
if( (*it).cnt > 0 ) (*it).sum = ((ll)((*it).cnt)*((*it).cnt)*(1+r-l))%mod;
else {
(*it).sum = 0;
if( l < r ) {
if( (*it).L != NULL ) (*it).sum = ((*it).sum + (*(*it).L).sum)%mod;
if( (*it).R != NULL ) (*it).sum = ((*it).sum + (*(*it).R).sum)%mod;
}
}
}
void solve() {
scanf("%d", &N);
for(int i=0; i<2*N; i+=2) {
int a, b, c, d, f;
scanf("%d %d %d %d %d", &a, &b, &c, &d, &f);
node[i] = Node(a-1, b, d, f);
node[i+1] = Node(c, b, d, -f);
}
interval IT = interval();
sort(node, node+N*2);
ll ans = 0;
int lastx = 0, x;
for(int i=0; i<2*N; i++) {
x = node[i].x;
ans = (ans + IT.sum*(x-lastx))%mod;
lastx = x;
insert(&IT, node[i].dn, node[i].up, 0, 1000000000, node[i].v);
}
printf("%lld\n", ans);
}
int main() {
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
4800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
