제출 #259229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259229		vioalbert	Nuclearia (CEOI15_nuclearia)	C++14	0 / 100	1104 ms	176876 KiB

nuclearia

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2500005;
ll w, h, n, q;
vector<vector<ll>> grid;
ll st[4*N], lazy[4*N];

void build(int idx, int l, int r) {
	if(l == r) {
		st[idx] = grid[1][l];
		lazy[idx] = 0;
		return;
	}
	int mid = (l+r)/2, lc = idx<<1, rc = idx<<1|1;
	build(lc, l, mid);
	build(rc, mid+1, r);
	st[idx] = st[lc] + st[rc];
}

void push(int idx, int l, int r) {
	if(l < r && lazy[idx]) {
		int mid = (l+r)/2, lc = idx<<1, rc = idx<<1|1;
		st[lc] += lazy[idx] * (mid - l + 1), lazy[lc] += lazy[idx];
		st[rc] += lazy[idx] * (r - mid), lazy[rc] += lazy[idx];
	}
	lazy[idx] = 0;
}

void update(int idx, int l, int r, int x, int y, ll val) {
	push(idx, l, r);
	if(r < x || y < l) return;
	if(x <= l && r <= y) {
		st[idx] += (r - l + 1) * val;
		lazy[idx] = val;
		return;
	}
	int mid = (l+r)/2, lc = idx<<1, rc = idx<<1|1;
	update(lc, l, mid, x, y, val);
	update(rc, mid+1, r, x, y, val);
	st[idx] = st[lc] + st[rc];
}

ll query(int idx, int l, int r, int x, int y) {
	push(idx, l, r);
	if(r < x || y < l) return 0;
	if(x <= l && r <= y) return st[idx];
	int mid = (l+r)/2, lc = idx<<1, rc = idx<<1|1;
	ll const lq = query(lc, l, mid, x, y);
	ll const rq = query(rc, mid+1, r, x, y);
	return lq + rq;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> w >> h >> n;
	grid.assign(h+1, vector<ll>(w+1, 0));
	build(1, 1, w);
	for(int i = 0; i < n; i++) {
		ll x, y, a, b; cin >> x >> y >> a >> b;
		ll len = (a + b - 1) / b;
		ll loc = (x - len + 1 < 1ll) ? 1 : (x - len + 1);
		ll fi = a - (x - loc) * b;
		// cerr << loc << ' ' << fi << '\n';
		update(1, 1, w, loc, loc, fi);
		if(loc + 1 <= x)
			update(1, 1, w, loc + 1, x, b);
		if(x + 1 <= w)
			update(1, 1, w, x + 1, min(w, x + len - 1), -b);
		if(x + len <= w)
			update(1, 1, w, x+len, x+len, -fi);
	}
	for(int i = 1; i <= w; i++) {
		grid[1][i] = query(1, 1, w, 1, i);
		// cerr << grid[1][i] << ' ';
	}
	// cerr << '\n';
	build(1, 1, w);

	cin >> q;
	while(q--) {
		ll r1, c1, r2, c2; cin >> c1 >> r1 >> c2 >> r2;
		// cerr << r1 << ' ' << c1 << ' ' << r2 << ' ' << c2 << '\n';
		double ans = query(1, 1, w, c1, c2);
		ans /= 1.0 * (r2 - r1 + 1) * (c2 - c1 + 1);
		cout << (ll)(ans+0.5) << '\n';
	}

	return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 2
• Subtask 3: 0 / 3
• Subtask 4: 0 / 2
• Subtask 5: 0 / 6
• Subtask 6: 0 / 4
• Subtask 7: 0 / 6
• Subtask 8: 0 / 4
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10
• Subtask 11: 0 / 15
• Subtask 12: 0 / 10
• Subtask 13: 0 / 12
• Subtask 14: 0 / 8