#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 tree[530000], lazy[530000];
void apply(int p, int v, int ps, int pe){
tree[p] += 1ll * (mod + v) * (vx[pe + 1] - vx[ps]) % mod;
lazy[p] += v;
tree[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);
tree[p] = tree[2*p] + tree[2*p+1];
}
int query(int s, int e, int ps, int pe, int p){
if(e < ps || pe < s) return 0;
if(s <= ps && pe <= e) return tree[p];
lazydown(p, ps, pe);
int pm = (ps + pe) / 2;
return (query(s, e, ps, pm, 2*p) + query(s, e, pm+1, pe, 2*p+1)) % mod;
}
}seg1, seg2;
int n;
struct swp{
int pos, s, e, x, idx;
bool operator<(const swp &a)const{
return pos < a.pos;
}
};
vector<swp> sweep;
lint inside[100005];
lint gap[100005];
int sx[100005], sy[100005], ex[100005], ey[100005], v[100005];
int main(){
scanf("%d",&n);
for(int i=0; i<n; i++){
//int sx, sy, ex, ey, v;
scanf("%d %d %d %d %d",&sx[i],&sy[i],&ex[i],&ey[i],&v[i]);
ex[i]++;
ey[i]++;
/*gap[i] = v;
sweep.push_back({sy, sx, ex+1, v, i});
sweep.push_back({ey+1, sx, ex+1, -v, i});
vx.push_back(sx);
vx.push_back(ex+1);*/
}
lint ret = 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int lx = min(ex[i], ex[j]) - max(sx[i], sx[j]);
int ly = min(ey[i], ey[j]) - max(sy[i], sy[j]);
if(lx > 0 && ly >= 0) ret += (1ll * lx * ly % mod) * v[i] * v[j] % 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) e++;
for(int j=i; j<e; j++){
auto t = sweep[j];
lint ins = seg1.query(t.s, t.e-1, 0, vx.size()-1, 1) * t.pos - seg2.query(t.s, t.e-1, 0, vx.size() - 1, 1);
ins = (ins % mod + mod) % mod;
seg1.add(t.s, t.e-1, 0, vx.size() - 1, 1, t.x);
seg2.add(t.s, t.e-1, 0, vx.size() - 1, 1, (mod + 1ll * t.pos * t.x % mod) % mod);
if(t.x > 0) inside[t.idx] += mod - ins;
else inside[t.idx] += ins;
}
i = e;
}
lint ret = 0;
for(int i=0; i<n; i++){
ret += gap[i] * inside[i] % mod;
ret %= mod;
}*/
printf("%lld",ret);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
21800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
