Submission #19091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19091	2016-02-18T06:09:07 Z	cki86201	Evaluation (kriii1_E)	C++	0 / 1	231 ms	40004 KB

E

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

const int MOD = 1e9 + 7;

struct line{
	line(){}
	line(int x,int y1,int y2,int v):x(x), y1(y1), y2(y2), v(v){}
	int x, y1, y2, v;
	bool operator<(const line &l)const{
		return x < l.x;
	}
}L[200010];

struct node{
	node(){x = u = 0, left = 0;}
	int x, u;
	int left;
}T[3000030];
int Z;

int update(int rt, int s, int d, int l, int r, int v){
	if(l <= s && d <= r){
		T[rt].u = (T[rt].u + v + MOD) % MOD;
		int tmp = T[rt].x;
		T[rt].x = (T[rt].x + (ll)(d-s+1) * v) % MOD;
		if(T[rt].x < 0)T[rt].x += MOD;
		return tmp;
	}
	int m = (s+d)>>1, res = 0;
	if(!T[rt].left)T[rt].left = ++Z; ++Z;
	if(l<=m){
		res += update(T[rt].left, s, m, l, r, v);
	}
	if(m<r){
		res += update(T[rt].left + 1, m+1, d, l, r, v);
	}
	T[rt].x = (T[rt].x + (ll)(min(d, r) - max(s, l) + 1) * v) % MOD;
	if(T[rt].x < 0)T[rt].x += MOD;
	res = (res + (ll)(min(d, r) - max(s, l) + 1) * T[rt].u) % MOD;
	return res;
}

int main(){
	int n; scanf("%d", &n);
	rep(i, n){
		int a, b, c, d, p;
		scanf("%d%d%d%d%d", &a, &b, &c, &d, &p);
		L[i+i] = line(a, b, d, p);
		L[i+i+1] = line(c+1, b, d, -p);
	}
	sort(L, L+n+n);
	int root = 0;
	ll ans = 0;
	ll now = 0;
	for(int i=0;i<n+n;i++){
		if(i != 0){
			ans += now * (L[i].x - L[i-1].x), ans %= MOD;
		}
		now += (ll)(L[i].y2 - L[i].y1 + 1) * L[i].v * L[i].v;
		now += 2LL * L[i].v * update(root, 1, 1e9, L[i].y1, L[i].y2, L[i].v);
		now %= MOD;
		if(now < 0)now += MOD;
	}
	printf("%lld", ans);
	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	40004 KB	Output is correct
2	Correct	4 ms	40004 KB	Output is correct
3	Correct	12 ms	40004 KB	Output is correct
4	Correct	13 ms	40004 KB	Output is correct
5	Correct	0 ms	40004 KB	Output is correct
6	Correct	0 ms	40004 KB	Output is correct
7	Correct	14 ms	40004 KB	Output is correct
8	Correct	14 ms	40004 KB	Output is correct
9	Correct	0 ms	40004 KB	Output is correct
10	Correct	12 ms	40004 KB	Output is correct
11	Correct	20 ms	40004 KB	Output is correct
12	Correct	29 ms	40004 KB	Output is correct
13	Correct	37 ms	40004 KB	Output is correct
14	Correct	33 ms	40004 KB	Output is correct
15	Correct	38 ms	40004 KB	Output is correct
16	Correct	196 ms	40004 KB	Output is correct
17	Correct	191 ms	40004 KB	Output is correct
18	Runtime error	231 ms	40000 KB	SIGSEGV Segmentation fault
19	Halted	0 ms	0 KB	-