Submission #19084

#	Time	Username	Problem	Language	Result	Execution time	Memory
19084		gs14004	Evaluation (kriii1_E)	C++14	1 / 1	832 ms	28584 KiB

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 / 1