Submission #19082

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19082	2016-02-18T04:50:22 Z	gs14004	Evaluation (kriii1_E)	C++14	1 / 1	1208 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);
			ins = (ins % mod + mod) % mod;
			if(t.x > 0) inside[t.idx] += mod - ins;
			else inside[t.idx] += ins;
			seg1.add(t.s, t.e-1, 0, vx.size()-2, 1, (mod + t.x) % mod);
			seg2.add(t.s, t.e-1, 0, vx.size()-2, 1, (mod + 1ll * t.pos * t.x % mod) % mod);
		}
		i = e;
	}
	lint ret = 0;
	for(int i=0; i<n; i++){
		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	0 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	0 ms	19872 KB	Output is correct
6	Correct	5 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	9 ms	19872 KB	Output is correct
10	Correct	6 ms	19872 KB	Output is correct
11	Correct	43 ms	20868 KB	Output is correct
12	Correct	67 ms	20868 KB	Output is correct
13	Correct	78 ms	20868 KB	Output is correct
14	Correct	103 ms	20868 KB	Output is correct
15	Correct	99 ms	20868 KB	Output is correct
16	Correct	409 ms	28580 KB	Output is correct
17	Correct	595 ms	28580 KB	Output is correct
18	Correct	800 ms	28580 KB	Output is correct
19	Correct	1164 ms	28580 KB	Output is correct
20	Correct	1208 ms	28580 KB	Output is correct