Submission #19074

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19074	2016-02-18T03:39:59 Z	gs14004	Evaluation (kriii1_E)	C++14	0 / 1	2000 ms	21800 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 * (mod + 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];
	}
	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 sx[100005], sy[100005], ex[100005], ey[100005], v[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[i],&sy[i],&ex[i],&ey[i],&v[i]);
		ex[i]++;
		ey[i]++;
		/*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);*/
	}
	lint ret = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			int lx = min(ex[i], ex[j]) - max(sx[i], sx[j]);
			int ly = min(ey[i], ey[j]) - max(sy[i], sy[j]);
			if(lx > 0 && ly > 0) ret += (1ll * lx * ly % mod) * v[i] * v[j] % 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) e++;
		for(int j=i; j<e; j++){
			auto t = sweep[j];
			lint ins = seg1.query(t.s, t.e-1, 0, vx.size()-1, 1) * t.pos - seg2.query(t.s, t.e-1, 0, vx.size() - 1, 1);
			ins = (ins % mod + mod) % mod;
			seg1.add(t.s, t.e-1, 0, vx.size() - 1, 1, t.x);
			seg2.add(t.s, t.e-1, 0, vx.size() - 1, 1, (mod + 1ll * t.pos * t.x % mod) % mod);
			if(t.x > 0) inside[t.idx] += mod - ins;
			else inside[t.idx] += ins;
		}
		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

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	21800 KB	Output is correct
2	Correct	0 ms	21800 KB	Output is correct
3	Correct	0 ms	21800 KB	Output is correct
4	Correct	0 ms	21800 KB	Output is correct
5	Correct	0 ms	21800 KB	Output is correct
6	Correct	11 ms	21800 KB	Output is correct
7	Correct	12 ms	21800 KB	Output is correct
8	Correct	11 ms	21800 KB	Output is correct
9	Correct	8 ms	21800 KB	Output is correct
10	Correct	11 ms	21800 KB	Output is correct
11	Correct	962 ms	21800 KB	Output is correct
12	Correct	1074 ms	21800 KB	Output is correct
13	Correct	984 ms	21800 KB	Output is correct
14	Correct	1075 ms	21800 KB	Output is correct
15	Correct	976 ms	21800 KB	Output is correct
16	Execution timed out	2000 ms	21796 KB	Program timed out
17	Halted	0 ms	0 KB	-