oj.uz

Submission #105391

# Submission time Handle Problem Language Result Execution time Memory
105391 2019-04-11T19:44:42 Z Noam527 Golf (JOI17_golf) C++17
100 / 100
 4481 ms 329148 KB 
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct rect {
	int t, b, l, r;
	rect() {}
	rect(int tt, int bb, int ll, int rr) : t(tt), b(bb), l(ll), r(rr) {}
};
// v(0) = insert, v(1) = delete, v(2) = query
struct eve {
	int v, t, l, r;
	eve() {}
	eve(int vv, int tt, int ll, int rr) : v(vv), t(tt), l(ll), r(rr) {}
	bool operator < (const eve &a) const {
		if (t != a.t) return t < a.t;
		return v < a.v;
	}
};
struct line {
	int d, l, r, i;
	line() {}
	line(int dd, int ll, int rr, int ii = 0) : d(dd), l(ll), r(rr), i(ii) {}
	bool operator < (const line &a) const {
		if (d != a.d) return d < a.d;
		if (l != a.l) return l < a.l;
		return r < a.r;
	}
	bool operator == (const line &a) const {
		return d == a.d && l == a.l && r == a.r;
	}
};
struct segtree {
	int n;
	vector<set<line>> t;
	segtree() {}
	segtree(int sz) {
		n = max(2, sz);
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n);
	}
	void add(const line &a) {
		add(a, 0, 0, 0, n - 1);
	}
	void erase(const line &a) {
		add(a, 1, 0, 0, n - 1);
	}
	void add(const line &a, int type, int node, int nl, int nr) {
		if (a.r < nl || nr < a.l) return;
		if (a.l <= nl && nr <= a.r) {
			if (type == 0) t[node].insert(a);
			else t[node].erase(a);
			return;
		}
		int mid = (nl + nr) / 2;
		add(a, type, 2 * node + 1, nl, mid);
		add(a, type, 2 * node + 2, mid + 1, nr);
	}
	line getrid(const line &a) {
		erase(a);
		return a;
	}
	line query(const line &a) {
		int pos = a.d + n - 1;
		set<line>::iterator it;
		line S(a.l, 0, 0, 0);
		if (OO) {
			cout << "find cut of " << a.d << " " << a.l << " " << a.r << '\n';
			cout << "in:\n";
			for (const auto &i : t[pos]) cout << i.d << " " << i.l << " " << i.r << '\n';
		}
		it = t[pos].lower_bound(S);
		if (it != t[pos].end() && it->d <= a.r) return getrid(*it);
		pos = (pos - 1) / 2;
		while (pos) {
			if (OO) {
				cout << "find cut of " << a.d << " " << a.l << " " << a.r << '\n';
				cout << "in:\n";
				for (const auto &i : t[pos]) cout << i.d << " " << i.l << " " << i.r << '\n';
			}
			it = t[pos].lower_bound(S);
			if (it != t[pos].end() && it->d <= a.r) return getrid(*it);
			pos = (pos - 1) / 2;
		}
		if (OO) {
			cout << "find cut of " << a.d << " " << a.l << " " << a.r << '\n';
			cout << "in:\n";
			for (const auto &i : t[pos]) cout << i.d << " " << i.l << " " << i.r << '\n';
		}
		it = t[pos].lower_bound(S);
		if (it != t[pos].end() && it->d <= a.r) return getrid(*it);
		return line(-1, -1, -1, -1);
	}
};

pair<int, int> st, en;
int n, MX, MY;
vector<rect> r;
vector<line> V, H;
segtree TV, TH;

vector<int> dv, dh;

void compress() {
	vector<int> compx, compy;
	compx.reserve(2 * n + 2);
	compy.reserve(2 * n + 2);
	compx.push_back(st.first), compx.push_back(en.first);
	compy.push_back(st.second), compy.push_back(en.second);
	for (auto &i : r) {
		compx.push_back(i.l), compx.push_back(i.r);
		compy.push_back(i.b), compy.push_back(i.t);
	}
	sort(compx.begin(), compx.end());
	sort(compy.begin(), compy.end());
	compx.resize(unique(compx.begin(), compx.end()) - compx.begin());
	compy.resize(unique(compy.begin(), compy.end()) - compy.begin());
	auto MP = [](const vector<int> &aa, int &value) {
		value = lower_bound(aa.begin(), aa.end(), value) - aa.begin();
	};
	MP(compx, st.first), MP(compx, en.first);
	MP(compy, st.second), MP(compy, en.second);
	for (auto &i : r) {
		MP(compx, i.l), MP(compx, i.r);
		MP(compy, i.b), MP(compy, i.t);
	}
	MX = compx.size();
	MY = compy.size();
}

void calc_vertical() {
	vector<eve> E;
	E.reserve(4 * n + 2);
	E.push_back(eve(2, st.first, st.second, st.second));
	E.push_back(eve(2, en.first, en.second, en.second));
	for (auto &i : r) {
		E.push_back(eve(0, i.l + 1, i.b, i.t));
		E.push_back(eve(2, i.l, i.b, i.b));
		E.push_back(eve(1, i.r, i.b, i.t));
		E.push_back(eve(2, i.r, i.b, i.b));
	}
	sort(E.begin(), E.end());
	set<pair<int, int>> bl;
	for (const auto &i : E) {
		if (i.v == 0)
			bl.insert({ i.l, i.r });
		else if (i.v == 1)
			bl.erase({ i.l, i.r });
		else {
			int lo, hi;
			auto it = bl.lower_bound({ i.l,i.l });
			if (it == bl.end()) hi = MY - 1;
			else hi = it->first;
			if (it == bl.begin()) lo = 0;
			else {
				it--;
				lo = it->second;
			}
			V.push_back(line(i.t, lo, hi));
		}
	}
	V.push_back(line(0, 0, MY - 1));
	V.push_back(line(MX - 1, 0, MY - 1));
	sort(V.begin(), V.end());
	V.resize(unique(V.begin(), V.end()) - V.begin());
	for (int i = 0; i < V.size(); i++) V[i].i = i;
}

void calc_horizontal() {
	vector<eve> E;
	E.reserve(3 * n + 2);
	E.push_back(eve(2, st.second, st.first, st.first));
	E.push_back(eve(2, en.second, en.first, en.first));
	for (auto &i : r) {
		E.push_back(eve(0, i.b + 1, i.l, i.r));
		E.push_back(eve(2, i.b, i.l, i.l));
		E.push_back(eve(1, i.t, i.l, i.r));
		E.push_back(eve(2, i.t, i.l, i.l));
	}
	sort(E.begin(), E.end());
	set<pair<int, int>> bl;
	for (const auto &i : E) {
		if (i.v == 0)
			bl.insert({ i.l, i.r });
		else if (i.v == 1)
			bl.erase({ i.l, i.r });
		else {
			int lo, hi;
			auto it = bl.lower_bound({ i.l,i.l });
			if (it == bl.end()) hi = MX - 1;
			else hi = it->first;
			if (it == bl.begin()) lo = 0;
			else {
				it--;
				lo = it->second;
			}
			H.push_back(line(i.t, lo, hi));
		}
	}
	H.push_back(line(0, 0, MX - 1));
	H.push_back(line(MY - 1, 0, MX - 1));
	sort(H.begin(), H.end());
	H.resize(unique(H.begin(), H.end()) - H.begin());
	for (int i = 0; i < H.size(); i++) H[i].i = i;
}

void bfs(int startv, int starth) {
	dv.resize(V.size(), -1);
	dh.resize(H.size(), -1);
	dv[startv] = dh[starth] = 0;
	TV.erase(V[startv]);
	TH.erase(H[starth]);
	queue<pair<int, int>> q;
	q.push({ startv, 0 });
	q.push({ starth, 1 });
	while (q.size()) {
		pair<int, int> x = q.front();
		q.pop();
		if (OO) {
			cout << "bfs on " << x.first << " " << x.second << '\n';
			cout << "with distance ";
			if (x.second == 0) cout << dv[x.first] << '\n';
			else cout << dh[x.first] << '\n';
		}
		if (x.second == 0) {
			// current is vertical
			line c = TH.query(V[x.first]);
			while (c.d != -1) {
				dh[c.i] = 1 + dv[x.first];
				q.push({ c.i, 1 });
				c = TH.query(V[x.first]);
			}
		}
		else {
			line c = TV.query(H[x.first]);
			while (c.d != -1) {
				dv[c.i] = 1 + dh[x.first];
				q.push({ c.i, 0 });
				c = TV.query(H[x.first]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> st.first >> st.second >> en.first >> en.second;
	cin >> n;
	r.resize(n);
	for (auto &i : r) cin >> i.l >> i.r >> i.b >> i.t;
	compress();
	calc_vertical();
	calc_horizontal();
	if (OO) {
		cout << "start " << st.first << " " << st.second << '\n';
		cout << "end " << en.first << " " << en.second << '\n';
		cout << "rectangles\n";
		for (const auto &i : r) {
			cout << i.l << " " << i.b << " " << i.r << " " << i.t << '\n';
		}
		cout << "verticals\n";
		for (const auto &i : V) cout << i.d << ", [" << i.l << " " << i.r << "]\n";
		cout << "horizontals\n";
		for (const auto &i : H) cout << i.d << ", [" << i.l << " " << i.r << "]\n";
	}

	TV = segtree(MY);
	TH = segtree(MX);
	for (const auto &i : V) TV.add(i);
	for (const auto &i : H) TH.add(i);
	int starth, startv, endh, endv;
	for (const auto &i : V) {
		if (i.d == st.first && i.l <= st.second && st.second <= i.r) startv = i.i;
		if (i.d == en.first && i.l <= en.second && en.second <= i.r) endv = i.i;
	}
	for (const auto &i : H) {
		if (i.d == st.second && i.l <= st.first && st.first <= i.r) starth = i.i;
		if (i.d == en.second && i.l <= en.first && en.first <= i.r) endh = i.i;
	}
	bfs(startv, starth);
	cout << 1 + min(dv[endv], dh[endh]) << '\n';
}

Compilation message

golf.cpp: In function 'void calc_vertical()':
golf.cpp:173:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) V[i].i = i;
                  ~~^~~~~~~~~~
golf.cpp: In function 'void calc_horizontal()':
golf.cpp:211:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < H.size(); i++) H[i].i = i;
                  ~~^~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:288:25: warning: 'endv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << 1 + min(dv[endv], dh[endh]) << '\n';
                         ^
golf.cpp:287:5: warning: 'startv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  bfs(startv, starth);
  ~~~^~~~~~~~~~~~~~~~
golf.cpp:288:35: warning: 'endh' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << 1 + min(dv[endv], dh[endh]) << '\n';
                                   ^
golf.cpp:287:5: warning: 'starth' may be used uninitialized in this function [-Wmaybe-uninitialized]
  bfs(startv, starth);
  ~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 360 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 12 ms 1664 KB Output is correct
6 Correct 12 ms 1664 KB Output is correct
7 Correct 13 ms 1664 KB Output is correct
8 Correct 14 ms 1664 KB Output is correct
9 Correct 21 ms 1664 KB Output is correct
10 Correct 13 ms 1664 KB Output is correct
11 Correct 13 ms 1792 KB Output is correct
12 Correct 12 ms 1664 KB Output is correct
13 Correct 12 ms 1664 KB Output is correct
14 Correct 15 ms 1792 KB Output is correct
15 Correct 8 ms 896 KB Output is correct
16 Correct 9 ms 1408 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 360 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 12 ms 1664 KB Output is correct
6 Correct 12 ms 1664 KB Output is correct
7 Correct 13 ms 1664 KB Output is correct
8 Correct 14 ms 1664 KB Output is correct
9 Correct 21 ms 1664 KB Output is correct
10 Correct 13 ms 1664 KB Output is correct
11 Correct 13 ms 1792 KB Output is correct
12 Correct 12 ms 1664 KB Output is correct
13 Correct 12 ms 1664 KB Output is correct
14 Correct 15 ms 1792 KB Output is correct
15 Correct 8 ms 896 KB Output is correct
16 Correct 9 ms 1408 KB Output is correct
17 Correct 17 ms 2432 KB Output is correct
18 Correct 26 ms 2432 KB Output is correct
19 Correct 15 ms 2432 KB Output is correct
20 Correct 18 ms 2560 KB Output is correct
21 Correct 15 ms 2432 KB Output is correct
22 Correct 27 ms 2560 KB Output is correct
23 Correct 16 ms 2560 KB Output is correct
24 Correct 24 ms 2432 KB Output is correct
25 Correct 15 ms 2432 KB Output is correct
26 Correct 15 ms 2432 KB Output is correct
27 Correct 10 ms 1024 KB Output is correct
28 Correct 10 ms 1536 KB Output is correct
29 Correct 16 ms 1536 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 360 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 12 ms 1664 KB Output is correct
6 Correct 12 ms 1664 KB Output is correct
7 Correct 13 ms 1664 KB Output is correct
8 Correct 14 ms 1664 KB Output is correct
9 Correct 21 ms 1664 KB Output is correct
10 Correct 13 ms 1664 KB Output is correct
11 Correct 13 ms 1792 KB Output is correct
12 Correct 12 ms 1664 KB Output is correct
13 Correct 12 ms 1664 KB Output is correct
14 Correct 15 ms 1792 KB Output is correct
15 Correct 8 ms 896 KB Output is correct
16 Correct 9 ms 1408 KB Output is correct
17 Correct 17 ms 2432 KB Output is correct
18 Correct 26 ms 2432 KB Output is correct
19 Correct 15 ms 2432 KB Output is correct
20 Correct 18 ms 2560 KB Output is correct
21 Correct 15 ms 2432 KB Output is correct
22 Correct 27 ms 2560 KB Output is correct
23 Correct 16 ms 2560 KB Output is correct
24 Correct 24 ms 2432 KB Output is correct
25 Correct 15 ms 2432 KB Output is correct
26 Correct 15 ms 2432 KB Output is correct
27 Correct 10 ms 1024 KB Output is correct
28 Correct 10 ms 1536 KB Output is correct
29 Correct 16 ms 1536 KB Output is correct
30 Correct 3863 ms 305744 KB Output is correct
31 Correct 4186 ms 306184 KB Output is correct
32 Correct 3814 ms 307468 KB Output is correct
33 Correct 4185 ms 308624 KB Output is correct
34 Correct 3906 ms 311328 KB Output is correct
35 Correct 4078 ms 311232 KB Output is correct
36 Correct 3895 ms 311160 KB Output is correct
37 Correct 3805 ms 309704 KB Output is correct
38 Correct 4481 ms 311268 KB Output is correct
39 Correct 4273 ms 310900 KB Output is correct
40 Correct 1952 ms 329148 KB Output is correct
41 Correct 1897 ms 328952 KB Output is correct
42 Correct 1682 ms 269792 KB Output is correct
43 Correct 1602 ms 245100 KB Output is correct
44 Correct 1818 ms 284612 KB Output is correct
45 Correct 1825 ms 284516 KB Output is correct
46 Correct 1814 ms 284520 KB Output is correct
47 Correct 1793 ms 284560 KB Output is correct
48 Correct 1705 ms 259456 KB Output is correct
49 Correct 1813 ms 271928 KB Output is correct
50 Correct 13 ms 1536 KB Output is correct
51 Correct 11 ms 1660 KB Output is correct
52 Correct 10 ms 1536 KB Output is correct