oj.uz

Submission #259235

# Submission time Handle Problem Language Result Execution time Memory
259235 2020-08-07T12:42:44 Z vioalbert Nuclearia (CEOI15_nuclearia) C++14
9 / 100
 1000 ms 173608 KB 
#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);
		// cerr << x+1 << ' ' << min(w, x+len-1) << '\n';
		if(x + 1 <= w)
			update(1, 1, w, x + 1, min(w, x + len - 1), -b);
		// cerr << x+len << ' ' << x+len << '\n';
		if(x + len <= w)
			update(1, 1, w, x+len, x+len, -(a%b!=0?(a%b):b));
	}
	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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 170760 KB Output is correct
2 Correct 100 ms 4728 KB Output is correct
3 Correct 71 ms 3960 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 170860 KB Output is correct
2 Correct 103 ms 4716 KB Output is correct

Subtask #3
0 / 3.0

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

Subtask #4
0 / 2.0

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

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 173608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 52192 KB Output is correct
2 Correct 98 ms 4728 KB Output is correct

Subtask #7
0 / 6.0

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

Subtask #8
0 / 4.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1110 ms 171528 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1111 ms 171528 KB Time limit exceeded

Subtask #11
0 / 15.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 12.0

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

Subtask #14
0 / 8.0

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