Submission #19084

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19084	2016-02-18T04:53:21 Z	gs14004	Evaluation (kriii1_E)	C++14	1 / 1	832 ms	28584 KB

E

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
 
vector<int> vx;
 
struct seg{
	lint tree[530000], lazy[530000];
	void apply(int p, int v, int ps, int pe){
		tree[p] += 1ll * v * (vx[pe+1] - vx[ps]);
		lazy[p] += v;
		tree[p] %= mod;
		lazy[p] %= mod;
	}
	void add(int s, int e, int ps, int pe, int p, int v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			apply(p, v, ps, pe);
			return;
		}
		int pm = (ps + pe) / 2;
		if(lazy[p]){
			apply(2*p, lazy[p], ps, pm);
			apply(2*p+1, lazy[p], pm+1, pe);
			lazy[p] = 0;
		}
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		tree[p] = (tree[2*p] + tree[2*p+1]) % mod;
	}
	int query(int s, int e, int ps, int pe, int p){
		if(e < ps || pe < s) return 0;
		if(s <= ps && pe <= e) return tree[p];
		int pm = (ps + pe) / 2;
		if(lazy[p]){
			apply(2*p, lazy[p], ps, pm);
			apply(2*p+1, lazy[p], pm+1, pe);
			lazy[p] = 0;
		}
		return (query(s, e, ps, pm, 2*p) + query(s, e, pm+1, pe, 2*p+1)) % mod;
	}
}seg1, seg2;
 
int n;
struct swp{
	int pos, s, e, x, idx;
	bool operator<(const swp &a)const{
		return pos < a.pos;
	}
};
 
vector<swp> sweep;
lint inside[100005];
lint gap[100005];

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		int sx, sy, ex, ey, v;
		scanf("%d %d %d %d %d",&sx,&sy,&ex,&ey,&v);
		gap[i] = v;
		sweep.push_back({sy, sx, ex+1, v, i});
		sweep.push_back({ey+1, sx, ex+1, -v, i});
		vx.push_back(sx);
		vx.push_back(ex+1);
	}
	sort(vx.begin(), vx.end());
	vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
	for(auto &i : sweep){
		i.s = lower_bound(vx.begin(), vx.end(), i.s) - vx.begin();
		i.e = lower_bound(vx.begin(), vx.end(), i.e) - vx.begin();
	}
	sort(sweep.begin(), sweep.end());
	for(int i=0; i<sweep.size(); ){
		int e = i;
		while(e < sweep.size() && sweep[i].pos == sweep[e].pos) e++;
		for(int j=i; j<e; j++){
			auto t = sweep[j];
			lint ins = 1ll * seg1.query(t.s, t.e-1, 0, vx.size()-2, 1) * t.pos - seg2.query(t.s, t.e-1, 0, vx.size()-2, 1);
			if(t.x > 0) inside[t.idx] -= ins;
			else inside[t.idx] += ins;
			t.x += mod;
			seg1.add(t.s, t.e-1, 0, vx.size()-2, 1, (t.x) % mod);
			seg2.add(t.s, t.e-1, 0, vx.size()-2, 1, (1ll * t.pos * t.x % mod) % mod);
		}
		i = e;
	}
	lint ret = 0;
	for(int i=0; i<n; i++){
		inside[i] %= mod;
		inside[i] += mod;
		ret += gap[i] * inside[i] % mod;
		ret %= mod;
	}
	printf("%lld",ret % mod);
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	19876 KB	Output is correct
2	Correct	0 ms	19876 KB	Output is correct
3	Correct	0 ms	19876 KB	Output is correct
4	Correct	0 ms	19876 KB	Output is correct
5	Correct	0 ms	19876 KB	Output is correct
6	Correct	4 ms	19876 KB	Output is correct
7	Correct	0 ms	19876 KB	Output is correct
8	Correct	6 ms	19876 KB	Output is correct
9	Correct	6 ms	19876 KB	Output is correct
10	Correct	7 ms	19876 KB	Output is correct
11	Correct	23 ms	20872 KB	Output is correct
12	Correct	41 ms	20872 KB	Output is correct
13	Correct	60 ms	20872 KB	Output is correct
14	Correct	72 ms	20872 KB	Output is correct
15	Correct	70 ms	20872 KB	Output is correct
16	Correct	277 ms	28584 KB	Output is correct
17	Correct	391 ms	28584 KB	Output is correct
18	Correct	567 ms	28584 KB	Output is correct
19	Correct	823 ms	28584 KB	Output is correct
20	Correct	832 ms	28584 KB	Output is correct