oj.uz

답안 #19092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19092 2016-02-18T06:09:50 Z cki86201 Evaluation (kriii1_E) C++
0 / 1
 225 ms 57580 KB 
#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[4500030];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 57580 KB Output is correct
2 Correct 14 ms 57580 KB Output is correct
3 Correct 3 ms 57580 KB Output is correct
4 Correct 13 ms 57580 KB Output is correct
5 Correct 18 ms 57580 KB Output is correct
6 Correct 19 ms 57580 KB Output is correct
7 Correct 4 ms 57580 KB Output is correct
8 Correct 20 ms 57580 KB Output is correct
9 Correct 3 ms 57580 KB Output is correct
10 Correct 4 ms 57580 KB Output is correct
11 Correct 35 ms 57580 KB Output is correct
12 Correct 23 ms 57580 KB Output is correct
13 Correct 41 ms 57580 KB Output is correct
14 Correct 30 ms 57580 KB Output is correct
15 Correct 60 ms 57580 KB Output is correct
16 Correct 196 ms 57580 KB Output is correct
17 Correct 225 ms 57580 KB Output is correct
18 Runtime error 213 ms 57576 KB SIGSEGV Segmentation fault
19 Halted 0 ms 0 KB -