#include<stdio.h>
#include<algorithm>
using namespace std;
long long Mod=1000000007;
struct SegTree{
SegTree(){
S=0,p=0,c1=c2=NULL;
}
long long S;
int p;
SegTree *c1,*c2;
};
struct Seg{
int x,y1,y2,p;
bool operator <(const Seg &p)const{
return x<p.x;
}
}Y[200001];
int n,i,c;
long long S,T,Res;
void push(int x,int y1,int y2,int p){
Y[c].x=x,Y[c].y1=y1,Y[c].y2=y2,Y[c].p=p;
c++;
}
void spread(SegTree *node,int b,int e,int m){
long long p=node->p;
node->p=0;
node->c1->S+=p*(m-b+1);
node->c2->S+=p*(e-m);
node->c1->p=node->c2->p=p;
}
void make_child(SegTree *node,long long k,int a,int b){
node->c1=new SegTree();
node->c2=new SegTree();
}
long long Sum(SegTree *node,int b,int e,int s,int l){
if(b==s && e==l){
return node->S;
}
int m=(b+e)>>1;
if(node->c1==NULL)make_child(node,node->S/(e-b+1),m-b+1,e-m);
if(node->p)spread(node,b,e,m);
long long ss=0;
if(m>=s){
ss+=Sum(node->c1,b,m,s,min(m,l));
}
if(m+1<=l){
ss+=Sum(node->c2,m+1,e,max(s,m+1),l);
}
return ss;
}
void Ins(SegTree *node,int b,int e,int s,int l,int p){
if(b==s && e==l){
node->S+=(long long)(e-b+1)*p;
node->p+=p;
return;
}
int m=(b+e)>>1;
if(node->c1==NULL)make_child(node,node->S/(e-b+1),m-b+1,e-m);
if(node->p)spread(node,b,e,m);
if(m>=s){
Ins(node->c1,b,m,s,min(m,l),p);
}
if(m+1<=l){
Ins(node->c2,m+1,e,max(s,m+1),l,p);
}
node->S=node->c1->S+node->c2->S;
}
int main()
{
int x1,y1,x2,y2,a;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&a);
push(x1,y1,y2,a);
push(x2+1,y1,y2,-a);
}
sort(Y,Y+c);
SegTree *root=new SegTree();
for(i=0;i<c;i++){
S+=(long long)(Y[i].y2-Y[i].y1+1)*Y[i].p*Y[i].p;
T=(Mod+Y[i].p)%Mod;
S+=Sum(root,0,1000000000,Y[i].y1,Y[i].y2)%Mod*T*2LL;
S%=Mod;
Ins(root,0,1000000000,Y[i].y1,Y[i].y2,Y[i].p);
if(i!=c-1 && Y[i].x!=Y[i+1].x){
Res+=S*(Y[i+1].x-Y[i].x);
Res%=Mod;
}
}
printf("%lld\n",Res);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
4336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
