Submission #3948

#	Time	Username	Problem	Language	Result	Execution time	Memory
3948		waps12b	Evaluation (kriii1_E)	C++98	0 / 1	0 ms	7928 KiB

E

#include <iostream>
#include <cstdio>
#include <algorithm>

#define mod 1000000007
using namespace std;
typedef long long ll;

struct Node{
	Node(){x=up=dn=v=0;}
	Node(ll _x, ll _dn, ll _up, ll _v) {
		x = _x; up = _up; dn = _dn, v = _v;
	}
	ll x, up, dn, v;
	bool operator<(const Node & A) const{
		if( x == A.x ) return v < A.v;
		return x < A.x;
	}
};

struct interval{
	interval() {
		cnt = sum = 0;
		L = R = NULL;
	}
	ll cnt, sum;
	interval *L, *R;
};

Node node[100000*2];
ll N;

void cquery(interval *it, ll l, ll r, ll t) {
	ll mid = (l+r)/2;
	if( (*it).L != NULL && (*(*it).L).sum > 0 ) cquery( (*it).L, l, mid, t+(*it).cnt );
	if( (*it).R != NULL && (*(*it).R).sum > 0 ) cquery( (*it).R, mid+1, r, t+(*it).cnt );
	(*it).sum = 0;
	ll Lv, Rv;
	ll Pow = (((*it).cnt+t)*((*it).cnt+t))%mod;
	Lv = Rv = 0;
	if( l < r ) {
		if( (*it).L != NULL ) {
			Lv = (*(*it).L).sum;
		}
		if( (*it).R != NULL ) {
			Rv = (*(*it).R).sum;
		}
		(*it).sum = (Lv+Rv)%mod;
	}
	if( (*it).cnt > 0 ) {
		if( Lv == 0 )	(*it).sum = ((*it).sum+Pow*(mid-l+1)%mod)%mod;
		if( Rv == 0 )	(*it).sum = ((*it).sum+Pow*(r-mid)%mod)%mod;
	}
}

void insert(interval *it, ll a, ll b, ll l, ll r, ll v, ll t) {
	ll mid = (l+r)/2;
	if( a <= l && r <= b ) {
		(*it).cnt = ((*it).cnt+v)%mod;
		if( a <= mid ) {
			if( (*it).L != NULL) cquery((*it).L, l, mid, t+(*it).cnt);
		}
		if( mid < b ) {
			if( (*it).R != NULL) cquery((*it).R, mid+1, r, t+(*it).cnt);
		}
	}
	else {
		if( a <= mid ) {
			if( (*it).L == NULL) (*it).L = new interval();
			insert((*it).L, a, b, l, mid, v, t+(*it).cnt);
		}
		if( mid < b ) {
			if( (*it).R == NULL) (*it).R = new interval();
			insert((*it).R, a, b, mid+1, r, v, t+(*it).cnt);
		}
	}
	(*it).sum = 0;
	ll Lv, Rv;
	ll Pow = (((*it).cnt+t)*((*it).cnt+t))%mod;
	Lv = Rv = 0;
	if( l < r ) {
		if( (*it).L != NULL ) {
			Lv = (*(*it).L).sum;
		}
		if( (*it).R != NULL ) {
			Rv = (*(*it).R).sum;
		}
		(*it).sum = (Lv+Rv)%mod;
	}
	if( (*it).cnt > 0 ) {
		if( Lv == 0 )	(*it).sum = ((*it).sum+Pow*(mid-l+1)%mod)%mod;
		if( Rv == 0 )	(*it).sum = ((*it).sum+Pow*(r-mid)%mod)%mod;
	}
}


void solve() {
	scanf("%lld", &N);
	for(int i=0; i<2*N; i+=2) {
		ll a, b, c, d, f;
		scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &d, &f);
		--a;	--b;
		node[i] = Node(a, b, d, f);
		node[i+1] = Node(c, b, d, -f);
	}
	interval IT = interval();
	sort(node, node+N*2);
	ll ans = 0;
	ll lastx = 0, x;
	for(int i=0; i<2*N; i++)  {
		x = node[i].x;
		ans = (ans + ((IT.sum%mod)*(x-lastx))%mod)%mod;
		lastx = x;
		insert(&IT, node[i].dn, node[i].up-1, 0, 10000000000, node[i].v, 0);
	}
	printf("%lld\n", ans);
}

int main() {
	solve();
	return 0;
}

• Subtask 1: 0 / 1