Submission #4649

#	Time	Username	Problem	Language	Result	Execution time	Memory
4649		cki86201	Evaluation (kriii1_E)	C++98	1 / 1	544 ms	13972 KiB

E

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef pair<int,ll> P;
#define Fi first
#define Se second

const ll M=1e9+7;

ll T[1<<19];
int C[1<<19],down[1<<19];

int in[200020][2],N;
int p[200020],ord[200020];
int X[200020],W[200020];
ll ans,now;

void Mod(ll &x)
{
	if(x>0)x = x%M;
	else x%=M,x+=M,x%=M;
}

void Mod(int &x)
{
	if(x>0)x = x%M;
	else x%=M,x+=M,x%=M;
}

bool comp0(const int &a,const int &b){return in[a][0]!=in[b][0]?in[a][0]<in[b][0]:a<b;}
bool comp1(const int &a,const int &b){return in[a][1]!=in[b][1]?in[a][1]<in[b][1]:a<b;}

void build(int s,int e,int t)
{
	if(s==e){
		down[t] = X[s];
		return;
	}
	int m = (s+e)>>1;
	build(s,m,t<<1);
	build(m+1,e,t<<1|1);
	down[t] = down[t<<1] + down[t<<1|1];
}

P update(int l,int r,int s,int e,int t,int u)
{
	P d=P(0,0);
	if(l<=s&&e<=r){
		d = P(down[t],T[t]);
		C[t] += u;
		T[t] += (ll)u*down[t];
		Mod(T[t]);
		return d;
	}
	int m = (s+e)>>1;
	if(l<=m){
		P tmp = update(l,r,s,m,t<<1,u);
		d.Fi += tmp.Fi, d.Se += tmp.Se;
	}
	if(r>m){
		P tmp = update(l,r,m+1,e,t<<1|1,u);
		d.Fi += tmp.Fi, d.Se += tmp.Se;
	}
	d.Se += (ll)d.Fi * C[t];
	T[t] += (ll)d.Fi * u;
	Mod(d.Fi), Mod(d.Se), Mod(T[t]);
	return d;
}

int main()
{
	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,comp0);
	for(i=0;i<2*N;i++){
		if(i)X[i]=in[ord[i]][0]-in[ord[i-1]][0];
		W[ord[i]]=i;
	}
	sort(ord,ord+2*N,comp1);
	build(1,2*N-1,1);
	for(i=0;i<2*N;i++){
		int x = ord[i]>>1;
		int a = W[2*x]+1, b = W[2*x+1], f = p[ord[i]]*((ord[i]&1)?-1:1);
		if(i)ans += now * (in[ord[i]][1] - in[ord[i-1]][1]);
		now += (ll)(in[2*x+1][0]-in[2*x][0])*f*f;
		now += 2LL*f*update(a,b,1,2*N-1,1,f).Se;
		Mod(now);
	}
	printf("%d",int(ans%M));
}

• Subtask 1: 1 / 1