Submission #19081

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19081	2016-02-18T04:48:03 Z	gs14004	Evaluation (kriii1_E)	C++14	1 / 1	1186 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;
		}
		for(int j=i; j<e; j++){
			auto t = sweep[j];
			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	8 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	42 ms	20868 KB	Output is correct
12	Correct	67 ms	20868 KB	Output is correct
13	Correct	85 ms	20868 KB	Output is correct
14	Correct	101 ms	20868 KB	Output is correct
15	Correct	97 ms	20868 KB	Output is correct
16	Correct	418 ms	28580 KB	Output is correct
17	Correct	580 ms	28580 KB	Output is correct
18	Correct	797 ms	28580 KB	Output is correct
19	Correct	1183 ms	28580 KB	Output is correct
20	Correct	1186 ms	28580 KB	Output is correct