Submission #105391

#	Time	Username	Problem	Language	Result	Execution time	Memory
105391		Noam527	Golf (JOI17_golf)	C++17	100 / 100	4481 ms	329148 KiB

golf

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70