Submission #3976

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3976	2013-08-31T09:49:08 Z	waps12b	Evaluation (kriii1_E)	C++	0 / 1	2000 ms	12280 KB

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( Pow > 0 ) {
		if( Lv == 0 )	(*it).sum = ((*it).sum+Pow*(mid-l+1))%mod;
		if( Rv == 0 )	(*it).sum = ((*it).sum+Pow*(r-mid))%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( Pow > 0 ) {
		if( Lv == 0 )	(*it).sum = ((*it).sum+Pow*(mid-l+1))%mod;
		if( Rv == 0 )	(*it).sum = ((*it).sum+Pow*(r-mid))%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*(x-lastx))%mod;
		lastx = x;
		insert(&IT, node[i].dn, node[i].up-1, 0, 1000000000, node[i].v, 0);
	}
	printf("%lld\n", ans);
}

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

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7928 KB	Output is correct
2	Correct	4 ms	7928 KB	Output is correct
3	Correct	0 ms	7928 KB	Output is correct
4	Correct	0 ms	8060 KB	Output is correct
5	Correct	8 ms	8192 KB	Output is correct
6	Correct	4 ms	7928 KB	Output is correct
7	Correct	16 ms	7928 KB	Output is correct
8	Correct	44 ms	8192 KB	Output is correct
9	Correct	172 ms	8984 KB	Output is correct
10	Correct	328 ms	10172 KB	Output is correct
11	Correct	32 ms	7928 KB	Output is correct
12	Correct	176 ms	7928 KB	Output is correct
13	Correct	1516 ms	8588 KB	Output is correct
14	Execution timed out	2000 ms	12280 KB	Program timed out
15	Halted	0 ms	0 KB	-