Submission #4638

#	Time	Username	Problem	Language	Result	Execution time	Memory
4638		cki86201	Evaluation (kriii1_E)	C++98	0 / 1	0 ms	4336 KiB

E

#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+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][0]--,in[2*i][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]+1, b = in[2*x+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,u);
		now %= M;
	}
	printf("%d",int(ans%M));
}

• Subtask 1: 0 / 1