Submission #594147

#	Time	Username	Problem	Language	Result	Execution time	Memory
594147		Bobaa	Golf (JOI17_golf)	C++17	0 / 100	4 ms	468 KiB

golf

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

const int maxn = 4e5 + 100; 
const int inf = 2e9 + 100; 
const int mod = 1e9 + 7; 

struct segtree {
	bool v; 
	int l, r; 
};

segtree p[maxn * 50]; 
int cnt; 

int create() {
	return cnt++; 
}

int build(int l, int r) {
	int t = create(); 
	if (l == r) return t; 
	int m = (l + r) / 2; 
	p[t].l = build(l, m); 
	p[t].r = build(m + 1, r); 
	return t; 
}

int upd(int cur, int l, int r, int id, int w) {
	int t = create(); 
	if (l == r) {
		p[t].v = w; 
		return t; 
	}
	int m = (l + r) / 2; 
	if (id <= m) {
		p[t].l = upd(p[cur].l, l, m, id, w); 
		p[t].r = p[cur].r; 
	} else {
		p[t].l = p[cur].l; 
		p[t].r = upd(p[cur].r, m + 1, r, id, w); 
	}
	p[t].v = (p[p[t].l].v | p[p[t].r].v); 
	return t; 
}

void get(int t, int tl, int tr, int l, int r, vector<int> &h) {
	if (l > r || !p[t].v) return; 
	if (tl == tr) {
		h.push_back(l); 
		p[t].v = 0;
		return; 
	}
	int m = (tl + tr) / 2; 
	get(p[t].l, tl, m, l, min(r, m), h); 
	get(p[t].r, m + 1, tr, max(l, m + 1), r, h); 
	p[t].v = (p[p[t].l].v | p[p[t].r].v); 
}

pair<int, int> strt, fin; 
int n; 
pair<pair<int, int>, pair<int, int>> rec[maxn]; 
map<int, int> mpik; 
vector<int> srt; 
vector<pair<int, pair<int, int>>> seg[2]; 
int d[maxn]; 
int q[maxn]; 
pair<int, int> bo[maxn]; 

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cin >> strt.first >> strt.second >> fin.first >> fin.second; 
	cin >> n; 
	for (int i = 0; i < n; i++) cin >> rec[i].first.first >> rec[i].first.second >> rec[i].second.first >> rec[i].second.second; 
	for (int t = 0; t < 2; t++) {
		vector<pair<int, pair<int, int>>> que; 
		for (int i = 0; i < n; i++) {
			que.push_back(make_pair(rec[i].second.first, rec[i].first)); 
			que.push_back(make_pair(rec[i].second.second, rec[i].first)); 
			que.push_back(make_pair(rec[i].second.first, make_pair(inf, rec[i].first.first))); 
			que.push_back(make_pair(rec[i].second.first, make_pair(inf, rec[i].first.second))); 
			que.push_back(make_pair(rec[i].second.second, make_pair(-inf, rec[i].first.first))); 
			que.push_back(make_pair(rec[i].second.second, make_pair(-inf, rec[i].first.second))); 
			swap(rec[i].first, rec[i].second); 
		}
		que.push_back(make_pair(strt.second, make_pair(strt.first, strt.first))); 
		que.push_back(make_pair(fin.second, make_pair(fin.first, fin.first))); 
		swap(strt.first, strt.second); 
		swap(fin.first, fin.second); 
		sort(que.begin(), que.end()); 
		set<int> st; 
		st.insert(-1); 
		st.insert(inf); 
		for (auto its : que) {
			if (its.second.first == -inf) st.erase(its.second.second); 
			else {
				if (its.second.first == inf) st.insert(its.second.second); 
				else {
					set<int>::iterator it = st.upper_bound(its.second.first); 
					it--; 
					int le = *it; 
					it = st.lower_bound(its.second.second); 
					seg[t].push_back(make_pair(its.first, make_pair(le, *it))); 
				}
			}
		}
		sort(seg[t].begin(), seg[t].end()); 
		seg[t].resize(unique(seg[t].begin(), seg[t].end()) - seg[t].begin()); 
	}
	n = seg[0].size() + seg[1].size(); 
	assert(n < maxn); 
	for (int t = 0; t < 2; t++) {
		for (int i = 0; i < seg[t].size(); i++) {
			int l = lower_bound(seg[!t].begin(), seg[!t].end(), make_pair(seg[t][i].second.first, make_pair(-inf, -inf))) - seg[!t].begin(); 
			int r = upper_bound(seg[!t].begin(), seg[!t].end(), make_pair(seg[t][i].second.second, make_pair(inf, inf))) - seg[!t].begin() - 1; 
			if (!t) {
				l += seg[0].size(); 
				r += seg[0].size(); 
			}
			bo[i + t * seg[0].size()] = make_pair(l, r); 
		}
		vector<pair<int, pair<int, int>>> que; 
		for (int i = 0; i < seg[t].size(); i++) que.push_back(make_pair(seg[t][i].first, make_pair(i + t * seg[0].size(), 0))); 
		for (int i = 0; i < seg[!t].size(); i++) {
			que.push_back(make_pair(seg[!t][i].second.first, make_pair(-inf, i + !t * seg[0].size()))); 
			que.push_back(make_pair(seg[!t][i].second.second, make_pair(inf, i + !t * seg[0].size()))); 
		}
		sort(que.begin(), que.end()); 
		int cur = build(0, n - 1); 
		for (auto its : que) {
			if (its.second.first == inf) cur = upd(cur, 0, n - 1, its.second.second, 1); 
			else {
				if (its.second.first == inf) cur = upd(cur, 0, n - 1, its.second.second, 0); 
				else q[its.second.first] = cur; 
			}
		}
	}
	for (int i = 0; i < n; i++) d[i] = -1; 
	int sta, stb, fina, finb; 
	for (int i = 0; i < seg[0].size(); i++) if (seg[0][i].first == strt.second && seg[0][i].second.first <= strt.first && seg[0][i].second.second >= strt.first) sta = i; 
	for (int i = 0; i < seg[1].size(); i++) if (seg[1][i].first == strt.first && seg[1][i].second.first <= strt.second && seg[1][i].second.second >= strt.second) stb = seg[0].size() + i; 
	for (int i = 0; i < seg[0].size(); i++) if (seg[0][i].first == fin.second && seg[0][i].second.first <= fin.first && seg[0][i].second.second >= fin.first) fina = i; 
	for (int i = 0; i < seg[1].size(); i++) if (seg[1][i].first == fin.first && seg[1][i].second.first <= fin.second && seg[1][i].second.second >= fin.second) finb = seg[0].size() + i; 
	d[sta] = 0; 
	d[stb] = 0; 
	queue<int> que; 
	que.push(sta); 
	que.push(stb); 
	while (!que.empty()) {
		int id = que.front(); 
		que.pop(); 
		if (id == fina || id == finb) {
			cout << d[id] + 1; 
			return 0; 
		}
		vector<int> g; 
		get(q[id], 0, n - 1, bo[id].first, bo[id].second, g); 
		for (int i : g) if (d[i] == -1) {
			d[i] = d[id] + 1; 
			que.push(i); 
		}
	}
	return 0; 
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i = 0; i < seg[t].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
golf.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for (int i = 0; i < seg[t].size(); i++) que.push_back(make_pair(seg[t][i].first, make_pair(i + t * seg[0].size(), 0)));
      |                   ~~^~~~~~~~~~~~~~~
golf.cpp:125:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for (int i = 0; i < seg[!t].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
golf.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  for (int i = 0; i < seg[0].size(); i++) if (seg[0][i].first == strt.second && seg[0][i].second.first <= strt.first && seg[0][i].second.second >= strt.first) sta = i;
      |                  ~~^~~~~~~~~~~~~~~
golf.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for (int i = 0; i < seg[1].size(); i++) if (seg[1][i].first == strt.first && seg[1][i].second.first <= strt.second && seg[1][i].second.second >= strt.second) stb = seg[0].size() + i;
      |                  ~~^~~~~~~~~~~~~~~
golf.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for (int i = 0; i < seg[0].size(); i++) if (seg[0][i].first == fin.second && seg[0][i].second.first <= fin.first && seg[0][i].second.second >= fin.first) fina = i;
      |                  ~~^~~~~~~~~~~~~~~
golf.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  for (int i = 0; i < seg[1].size(); i++) if (seg[1][i].first == fin.first && seg[1][i].second.first <= fin.second && seg[1][i].second.second >= fin.second) finb = seg[0].size() + i;
      |                  ~~^~~~~~~~~~~~~~~
golf.cpp:153:10: warning: 'fina' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |   if (id == fina || id == finb) {
      |       ~~~^~~~~~~
golf.cpp:153:24: warning: 'finb' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |   if (id == fina || id == finb) {
      |                     ~~~^~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70