Submission #19093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19093	2016-02-18T06:11:16 Z	cki86201	Evaluation (kriii1_E)	C++	0 / 1	206 ms	63440 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[5000030];
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	8 ms	63440 KB	Output is correct
2	Correct	8 ms	63440 KB	Output is correct
3	Correct	8 ms	63440 KB	Output is correct
4	Correct	3 ms	63440 KB	Output is correct
5	Correct	16 ms	63440 KB	Output is correct
6	Correct	17 ms	63440 KB	Output is correct
7	Correct	18 ms	63440 KB	Output is correct
8	Correct	0 ms	63440 KB	Output is correct
9	Correct	23 ms	63440 KB	Output is correct
10	Correct	24 ms	63440 KB	Output is correct
11	Correct	37 ms	63440 KB	Output is correct
12	Correct	41 ms	63440 KB	Output is correct
13	Correct	40 ms	63440 KB	Output is correct
14	Correct	31 ms	63440 KB	Output is correct
15	Correct	57 ms	63440 KB	Output is correct
16	Correct	183 ms	63440 KB	Output is correct
17	Correct	198 ms	63440 KB	Output is correct
18	Runtime error	206 ms	63436 KB	SIGSEGV Segmentation fault
19	Halted	0 ms	0 KB	-