Submission #3517

#	Time	Username	Problem	Language	Result	Execution time	Memory
3517		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;
    }
} node[100000*2];

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

ll N;

void insert(interval *it, ll a, ll b, ll l, ll r, ll v) {
	if( a <= l && r <= b ) (*it).cnt = ((*it).cnt+v)%mod;            
    else {
        ll mid = (l+r)/2;
        if( a <= mid ) {
			if( (*it).L == NULL) (*it).L = new interval();
			insert((*it).L, a, b, l, mid, v);
		}
		if( mid < b ) {
			if( (*it).R == NULL) (*it).R = new interval();
			insert((*it).R, a, b, mid+1, r, v);
		}
	}
	if( (*it).cnt > 0 ) (*it).sum = ((ll)((((*it).cnt)*((*it).cnt))%mod)*(1+r-l))%mod;
    else {
		(*it).sum = 0;
        if( l < r ) {
			if( (*it).L != NULL ) (*it).sum	= ((*it).sum + (*(*it).L).sum%mod)%mod;
			if( (*it).R != NULL ) (*it).sum	= ((*it).sum + (*(*it).R).sum%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);
		node[i] = Node(a-1, 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;
		lastx = x;
		insert(&IT, node[i].dn, node[i].up, 0, 1000000000, node[i].v);
	}
	printf("%lld\n", ans);
}

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

• Subtask 1: 0 / 1