Submission #4642

#TimeUsernameProblemLanguageResultExecution timeMemory
4642cki86201Evaluation (kriii1_E)C++98
0 / 1
0 ms4336 KiB
#include<stdio.h> #include<stdlib.h> #include<algorithm> using namespace std; typedef long long ll; const ll M = 1e9+7; struct node{ node(){x=c=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; int y = u>0?u:M-u; now += 2*y*update(tree,a,b,1,1e9,u); now %= M; } printf("%d",int(ans%M)); }
#Verdict Execution timeMemoryGrader output
Fetching results...