Submission #19054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19054	2016-02-17T14:12:40 Z	gs14004	Evaluation (kriii1_E)	C++14	0 / 1	0 ms	8072 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 tree1[270000], tree2[270000], lazy[270000];
	void apply(int p, int v, int ps, int pe){
		if(v > 0){
			tree2[p] += (tree1[p] * v % mod);
			tree1[p] += 1ll * v * (vx[pe+1] - vx[ps]) % mod;
		}
		else{
			tree1[p] += 1ll * (mod + v) * (vx[pe + 1] - vx[ps]) % mod;
			tree2[p] += (tree1[p] * (mod + v) % mod);
		}
		lazy[p] += v;
		tree2[p] %= mod;
		tree1[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);
		tree1[p] = tree1[2*p] + tree1[2*p+1];
		tree2[p] = tree2[2*p] + tree2[2*p+1];
	}
}seg;

int n;
struct swp{
	int pos, s, e, x;
	bool operator<(const swp &a)const{
		return pos < a.pos;
	}
};

vector<swp> sweep;

int main(){
	scanf("%d",&n);
	lint ret = 0;
	for(int i=0; i<n; i++){
		int sx, sy, ex, ey, v;
		scanf("%d %d %d %d %d",&sx,&sy,&ex,&ey,&v);
		sweep.push_back({sy, sx, ex+1, v});
		sweep.push_back({ey+1, sx, ex+1, -v});
		vx.push_back(sx);
		vx.push_back(ex+1);
		ret += (1ll * (ex - sx + 1) * (ey - sy + 1) % mod) * v * v % mod;
		ret %= mod;
	}
	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){
			seg.add(sweep[e].s, sweep[e].e-1, 0, vx.size()-1, 1, sweep[e].x);
			e++;
		}
		if(e != sweep.size()){
			//printf("%d %d %lld\n",sweep[i].pos, sweep[e].pos, seg.tree2[1]);
			ret += 2ll * (sweep[e].pos - sweep[i].pos) * seg.tree2[1] % mod;
			ret %= mod;
		}
		i = e;
	}
	printf("%lld",ret);
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	8072 KB	Output isn't correct
2	Halted	0 ms	0 KB	-