#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll M = 1e9+7;
struct node{
node(){x=0,L=0LL,left=right=NULL;}
int x,c;
long long L;
node *left,*right;
}*tree;
ll update(node *R,int l,int r,int s,int e,int u){
if(l<=s&&e<=r){
R->c+=u;
ll tmp = R->L;
R->L += (ll)(e-s+1)*u;
R->L %= M;
return tmp;
}
int m = (s+e)>>1;
ll d=0;
if(l<=m){
if(!R->left)R->left = new node();
d += update(R->left,l,r,s,m,u);
}
if(r>m){
if(!R->right)R->right = new node();
d += update(R->right,l,r,m+1,e,u);
}
R->L += (ll)(min(e,r)-max(l,s)+1)*u;
R->L %= M;
return (d+(ll)R->c*(min(e,r)-max(l,s)+1))%M;
}
int in[200020][2],N;
int p[200020],ord[200020];
ll ans,now;
bool comp(const int &a,const int &b){return in[a][0]<in[b][0];}
int main()
{
tree = new node();
scanf("%d",&N);
int i;
for(i=0;i<N;i++){
scanf("%d%d%d%d%d",in[2*i],in[2*i]+1,in[2*i+1],in[2*i+1]+1,p+2*i);
p[2*i+1]=p[2*i];
in[2*i+1][0]++,in[2*i+1][1]++;
ord[2*i]=2*i,ord[2*i+1]=2*i+1;
}
sort(ord,ord+2*N,comp);
for(i=0;i<2*N;i++){
int x = ord[i]/2, u = p[ord[i]] * ((ord[i]&1)?-1:1);
int a = in[2*x][1], b = in[2*x+1][1]-1;
if(i)ans += now*(in[ord[i]][0]-in[ord[i-1]][0]);
now += (ll)(b-a+1)*u*u;
now += 2*u*update(tree,a,b,1,1e9+1,u);
now %= M;
}
printf("%d",int(ans%M));
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
4336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4336 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
4336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
