oj.uz

Submission #814101

# Submission time Handle Problem Language Result Execution time Memory
814101 2023-08-08T05:31:39 Z GEN 이지후(#10370) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 471 ms 152848 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXN = 100005;
const int MAXT = 10000000;

using pi = array<lint, 2>;

vector<int> v;

struct event {
	int x, s, e;
	lint val;
	bool operator<(const event &b) const { return x < b.x; }
	bool operator>(const event &b) const { return x > b.x; }
};

struct node {
	int l, r;
	array<array<lint, 2>, 2> sum;
} tree[MAXT];

int root[MAXN], piv;

int newnode() { return ++piv; }

void init(int s, int e, int p) {
	if (s == e)
		return;
	int m = (s + e) / 2;
	tree[p].l = newnode();
	tree[p].r = newnode();
	init(s, m, tree[p].l);
	init(m + 1, e, tree[p].r);
}

void add(int pos, int s, int e, int prv, int cur, array<array<lint, 2>, 2> v) {
	if (s == e) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				tree[cur].sum[i][j] = tree[prv].sum[i][j] + v[i][j];
			}
		}
		return;
	}
	int m = (s + e) / 2;
	if (pos <= m) {
		tree[cur].l = newnode();
		tree[cur].r = tree[prv].r;
		add(pos, s, m, tree[prv].l, tree[cur].l, v);
	} else {
		tree[cur].l = tree[prv].l;
		tree[cur].r = newnode();
		add(pos, m + 1, e, tree[prv].r, tree[cur].r, v);
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			tree[cur].sum[i][j] = tree[tree[cur].l].sum[i][j] + tree[tree[cur].r].sum[i][j];
		}
	}
}

array<array<lint, 2>, 2> query(int s, int e, int ps, int pe, int p) {
	if (e < ps || pe < s) {
		return {pi{0, 0}, pi{0, 0}};
	}
	if (s <= ps && pe <= e) {
		return tree[p].sum;
	}
	int pm = (ps + pe) / 2;
	auto q1 = query(s, e, ps, pm, tree[p].l);
	auto q2 = query(s, e, pm + 1, pe, tree[p].r);
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			q1[i][j] += q2[i][j];
		}
	}
	return q1;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int r, c, n, q, mod;
	cin >> r >> c >> n >> q >> mod;
	vector<event> rect;
	for (int i = 0; i < n; i++) {
		int x1, y1, x2, y2, w = 1;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2)
			swap(x1, x2);
		if (y1 > y2)
			swap(y1, y2);
		rect.push_back({x1, y1, y2, lint(w)});
		rect.push_back({x2, y1, y2, -lint(w)});
		v.push_back(y1);
		v.push_back(y2);
	}
	sort(all(rect));
	sort(all(v));
	v.resize(unique(all(v)) - v.begin());
	for (auto &x : rect) {
		x.s = lower_bound(all(v), x.s) - v.begin();
		x.e = lower_bound(all(v), x.e) - v.begin();
	}
	root[0] = newnode();
	init(0, sz(v) - 1, root[0]);
	auto Add = [&](int prv, int cur, int s, int e, lint v1, lint v2) {
		array<array<lint, 2>, 2> u1 = {pi{v1, -v1 * v[s]}, pi{v2, -v2 * v[s]}};
		array<array<lint, 2>, 2> u2 = {pi{-v1, v1 * v[e]}, pi{-v2, v2 * v[e]}};
		int wcur = newnode();
		add(s, 0, sz(v) - 1, prv, wcur, u1);
		add(e, 0, sz(v) - 1, wcur, cur, u2);
	};
	for (int i = 0; i < sz(rect); i++) {
		root[i + 1] = newnode();
		Add(root[i], root[i + 1], rect[i].s, rect[i].e, rect[i].val, -1ll * rect[i].val * rect[i].x);
	}
	auto Aux = [&](int root, int x, int e) {
		int pos = lower_bound(all(v), e) - v.begin();
		auto quer = query(0, pos - 1, 0, sz(v) - 1, root);
		lint sum0 = quer[0][0] * e + quer[0][1];
		lint sum1 = quer[1][0] * e + quer[1][1];
		return sum0 * x + sum1;
	};
	auto Query = [&](lint x, lint s, lint e) {
		int pos = upper_bound(all(rect), (event){(int)x, -1, -1}) - rect.begin();
		pos = root[pos];
		return Aux(pos, x, e) - Aux(pos, x, s);
	};
	lint l = 0;
	for (int i = 0; i < q; i++) {
		int x1, y1, x2, y2, vv;
		cin >> x1 >> y1 >> x2 >> y2 >> vv;
		x1 = (x1 + l * vv) % mod;
		x2 = (x2 + l * vv) % mod;
		y1 = (y1 + l * vv) % mod;
		y2 = (y2 + l * vv) % mod;
		if (x1 > x2)
			swap(x1, x2);
		if (y1 > y2)
			swap(y1, y2);
		l = Query(x2, y1, y2) - Query(x1, y1, y2);
		cout << l << "\n";
		l %= mod;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 18 ms 10868 KB Output is correct
5 Correct 19 ms 10876 KB Output is correct
6 Correct 16 ms 10272 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 18 ms 10868 KB Output is correct
5 Correct 19 ms 10876 KB Output is correct
6 Correct 16 ms 10272 KB Output is correct
7 Correct 165 ms 136696 KB Output is correct
8 Correct 459 ms 147732 KB Output is correct
9 Correct 240 ms 138756 KB Output is correct
10 Correct 374 ms 146232 KB Output is correct
11 Correct 278 ms 136284 KB Output is correct
12 Correct 291 ms 147648 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 18 ms 10868 KB Output is correct
5 Correct 19 ms 10876 KB Output is correct
6 Correct 16 ms 10272 KB Output is correct
7 Correct 174 ms 134724 KB Output is correct
8 Correct 428 ms 146400 KB Output is correct
9 Correct 240 ms 138996 KB Output is correct
10 Correct 390 ms 145044 KB Output is correct
11 Correct 271 ms 135528 KB Output is correct
12 Correct 296 ms 146400 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 18 ms 10868 KB Output is correct
5 Correct 19 ms 10876 KB Output is correct
6 Correct 16 ms 10272 KB Output is correct
7 Correct 165 ms 136696 KB Output is correct
8 Correct 459 ms 147732 KB Output is correct
9 Correct 240 ms 138756 KB Output is correct
10 Correct 374 ms 146232 KB Output is correct
11 Correct 278 ms 136284 KB Output is correct
12 Correct 291 ms 147648 KB Output is correct
13 Correct 174 ms 134724 KB Output is correct
14 Correct 428 ms 146400 KB Output is correct
15 Correct 240 ms 138996 KB Output is correct
16 Correct 390 ms 145044 KB Output is correct
17 Correct 271 ms 135528 KB Output is correct
18 Correct 296 ms 146400 KB Output is correct
19 Correct 197 ms 147936 KB Output is correct
20 Correct 449 ms 151100 KB Output is correct
21 Correct 242 ms 139100 KB Output is correct
22 Correct 381 ms 149620 KB Output is correct
23 Correct 278 ms 139644 KB Output is correct
24 Correct 297 ms 150972 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 129300 KB Output is correct
2 Correct 415 ms 142044 KB Output is correct
3 Correct 251 ms 138896 KB Output is correct
4 Correct 373 ms 141272 KB Output is correct
5 Correct 262 ms 133500 KB Output is correct
6 Correct 299 ms 142036 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 129300 KB Output is correct
2 Correct 415 ms 142044 KB Output is correct
3 Correct 251 ms 138896 KB Output is correct
4 Correct 373 ms 141272 KB Output is correct
5 Correct 262 ms 133500 KB Output is correct
6 Correct 299 ms 142036 KB Output is correct
7 Correct 203 ms 147976 KB Output is correct
8 Correct 471 ms 152848 KB Output is correct
9 Correct 238 ms 139072 KB Output is correct
10 Correct 419 ms 150284 KB Output is correct
11 Correct 282 ms 141484 KB Output is correct
12 Correct 305 ms 152836 KB Output is correct