#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
vector<int> vx;
struct seg{
lint tree1[270000], tree2[270000], lazy[270000];
void apply(int p, int v, int ps, int pe){
if(v > 0){
tree2[p] += (tree1[p] * v % mod);
tree1[p] += 1ll * v * (vx[pe+1] - vx[ps]) % mod;
}
else{
tree1[p] += 1ll * (mod - v) * (vx[pe + 1] - vx[ps]) % mod;
tree2[p] += (tree1[p] * (mod - v) % mod);
}
lazy[p] += v;
tree2[p] %= mod;
tree1[p] %= mod;
lazy[p] %= mod;
}
void lazydown(int p, int ps, int pe){
int pm = (ps + pe) / 2;
apply(2*p, lazy[p], ps, pm);
apply(2*p+1, lazy[p], pm+1, pe);
lazy[p] = 0;
}
void add(int s, int e, int ps, int pe, int p, int v){
if(e < ps || pe < s) return;
if(s <= ps && pe <= e){
apply(p, v, ps, pe);
return;
}
int pm = (ps + pe) / 2;
lazydown(p, ps, pe);
add(s, e, ps, pm, 2*p, v);
add(s, e, pm+1, pe, 2*p+1, v);
tree1[p] = tree1[2*p] + tree1[2*p+1];
tree2[p] = tree2[2*p] + tree2[2*p+1];
}
}seg;
int n;
struct swp{
int pos, s, e, x;
bool operator<(const swp &a)const{
return pos < a.pos;
}
};
vector<swp> sweep;
int main(){
scanf("%d",&n);
lint ret = 0;
for(int i=0; i<n; i++){
int sx, sy, ex, ey, v;
scanf("%d %d %d %d %d",&sx,&sy,&ex,&ey,&v);
sweep.push_back({sy, sx, ex+1, v});
sweep.push_back({ey+1, sx, ex+1, -v});
vx.push_back(sx);
vx.push_back(ex+1);
ret += (1ll * (ex - sx + 1) * (ey - sy + 1) % mod) * v * v % mod;
ret %= mod;
}
sort(vx.begin(), vx.end());
vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
for(auto &i : sweep){
i.s = lower_bound(vx.begin(), vx.end(), i.s) - vx.begin();
i.e = lower_bound(vx.begin(), vx.end(), i.e) - vx.begin();
}
sort(sweep.begin(), sweep.end());
for(int i=0; i<sweep.size(); ){
int e = i;
while(e < sweep.size() && sweep[i].pos == sweep[e].pos){
seg.add(sweep[e].s, sweep[e].e-1, 0, vx.size()-1, 1, sweep[e].x);
e++;
}
if(e != sweep.size()){
//printf("%d %d %lld\n",sweep[i].pos, sweep[e].pos, seg.tree2[1]);
ret += 2ll * (sweep[e].pos - sweep[i].pos) * seg.tree2[1] % mod;
ret %= mod;
}
i = e;
}
printf("%lld",ret);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
8072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
