Submission #19083

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19083	2016-02-18T04:52:12 Z	gs14004	Evaluation (kriii1_E)	C++14	1 / 1	1197 ms	28580 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]) % mod;
		lazy[p] += v;
		tree[p] %= mod;
		lazy[p] %= mod;
	}
	void lazydown(int p, int ps, int pe){
		int pm = (ps + pe) / 2;
		apply(2*p, lazy[p], ps, pm);
		apply(2*p+1, lazy[p], pm+1, pe);
		lazy[p] = 0;
	}
	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;
		lazydown(p, ps, pe);
		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];
		lazydown(p, ps, pe);
		int pm = (ps + pe) / 2;
		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	19872 KB	Output is correct
2	Correct	2 ms	19872 KB	Output is correct
3	Correct	0 ms	19872 KB	Output is correct
4	Correct	0 ms	19872 KB	Output is correct
5	Correct	2 ms	19872 KB	Output is correct
6	Correct	6 ms	19872 KB	Output is correct
7	Correct	8 ms	19872 KB	Output is correct
8	Correct	4 ms	19872 KB	Output is correct
9	Correct	4 ms	19872 KB	Output is correct
10	Correct	8 ms	19872 KB	Output is correct
11	Correct	35 ms	20868 KB	Output is correct
12	Correct	67 ms	20868 KB	Output is correct
13	Correct	86 ms	20868 KB	Output is correct
14	Correct	100 ms	20868 KB	Output is correct
15	Correct	93 ms	20868 KB	Output is correct
16	Correct	420 ms	28580 KB	Output is correct
17	Correct	597 ms	28580 KB	Output is correct
18	Correct	814 ms	28580 KB	Output is correct
19	Correct	1160 ms	28580 KB	Output is correct
20	Correct	1197 ms	28580 KB	Output is correct