제출 #4644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4644		cki86201	Evaluation (kriii1_E)	C++98	0 / 1	500 ms	65536 KiB

E

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
//F**king MLE
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+M)%M;
		now+=2*y*update(tree,a,b,1,1e9,u);
		now%=M;
	}
	printf("%d",int(ans%M));
}

• Subtask 1: 0 / 1