제출 #586908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586908		dutinmeow	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	347 ms	27924 KiB

Main

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

#pragma region debug

#if defined(LOCAL) && !defined(ONLINE_JUDGE)
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if (v.size()) {
		os << *v.begin();
		for (auto i = next(v.begin()); i != v.end(); i++)
		os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
	os << '[';
	if (d.size()) {
		os << *d.begin();
		for (auto i = next(d.begin()); i != d.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
	os << '[';
	if (s.size()) {
		int n = s.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = s.top();
			s.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
		}
	return os << "]>";
}

template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
	os << '[';
	if (q.size()) {
		int n = q.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = q.front();
			q.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
	os << '[';
	if (N) {
		os << *a.begin();
		for (auto i = next(a.begin()); i != a.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

map<char, string> _dbg_dict {
	{'1', "--------------------------------"},
	{'2', "================================"},
	{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
	{'4', "################################"},
	{'*', "********************************"},
	{'_', "_"},
	{'<', "<!---- "},
	{'>', " ----!>"},
	{'(', "(!==== "},
	{')', "==== !)"},
	{'[', "[!≡≡≡≡ "},
	{']', " ≡≡≡≡!]"},
	{'{', "{!#### "},
	{'}', " ####!}"},
	{'c', "checkpoint "},
	{'l', "line "},
	{'n', "\n"},
	{'t', "\t"}
};

template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }

void _dbg_print(string var, const char *a) {
	int n = strlen(a);
	for (int i = 0; i < n; i++) 
 cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}

#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
	dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define cerr if (false) cerr
#define dbg(...)
#endif

#pragma endregion debug

const int $L = 7;

int main() {
	int N, K, M;
	cin >> N >> K >> M;

	array<vector<int>, $L> lb, rb;
	lb.fill(vector<int>(2 * N, -1));
	rb.fill(vector<int>(2 * N, -1));

	vector<int> A(M), B(M);
	for (int i = 0; i < M; i++) {
		cin >> A[i] >> B[i];
		A[i]--, B[i]--;
	}
	
	multiset<int> mse;
	vector<vector<int>> ins(N), era(N);

	for (int i = 0; i < M; i++) {
		if (A[i] > B[i]) {
			ins[A[i]].push_back(B[i]);
			era[max(A[i] - K + 1, B[i] + 1)].push_back(B[i]);
		}
		// if (A[i] < B[i]) {
		// 	ins[min(A[i] + K - 1, B[i] - 1)].push_back(A[i]);
		// 	era[A[i]].push_back(A[i]);
		// }
	}
	for (int i = N - 1; i >= 0; i--) {
		for (int k : ins[i])
			mse.insert(k);
		ins[i].clear();
		lb[0][i + N] = min(i, mse.empty() ? N : *mse.begin());
		for (int k : era[i])
			mse.erase(mse.find(k));
		era[i].clear();
	}
	assert(mse.empty());

	for (int i = 0; i < M; i++) {
		if (A[i] < B[i]) {
			ins[A[i]].push_back(B[i]);
			era[min(A[i] + K - 1, B[i] - 1)].push_back(B[i]);
		} 
		// if (A[i] > B[i]) {
		// 	ins[max(A[i] - K + 1, B[i] + 1)].push_back(A[i]);
		// 	era[A[i]].push_back(A[i]);
		// }
	}
	for (int i = 0; i < N; i++) {
		for (int k : ins[i])
			mse.insert(k);
		ins[i].clear();
		rb[0][i + N] = max(i, mse.empty() ? 0 : *mse.rbegin());
		for (int k : era[i])
			mse.erase(mse.find(k));
		era[i].clear();
	}
	assert(mse.empty());

	for (int b = 1; b < $L; b++) {
		for (int i = N - 1; i >= 1; i--) {
			lb[b - 1][i] = min(lb[b - 1][i * 2], lb[b - 1][i * 2 + 1]);
			rb[b - 1][i] = max(rb[b - 1][i * 2], rb[b - 1][i * 2 + 1]);
		}
		for (int i = 0; i < N; i++) {
			int l = lb[b - 1][i + N], r = rb[b - 1][i + N];
			int retl = N, retr = 0;
			for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
				if (l & 1) {
					retl = min(retl, lb[b - 1][l]);
					retr = max(retr, rb[b - 1][l]);
					l++;
				}
				if (r & 1) {
					r--;
					retl = min(retl, lb[b - 1][r]);
					retr = max(retr, rb[b - 1][r]);
				}
			} 
			lb[b][i + N] = retl, rb[b][i + N] = retr;
		}
	}

	// for (int i = 0; i < $L; i++) {
	// 	vector<int> l(lb[i].begin() + N, lb[i].end());
	// 	vector<int> r(rb[i].begin() + N, rb[i].end());
	// 	dbg("_1\n", i, l, r);
	// }

	int Q;
	cin >> Q;
	while (Q--) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		if (v < lb[$L - 1][u + N] || rb[$L - 1][u + N] < v) {
			cout << -1 << '\n';
		} else {
			if (u == v) {
				cout << 0 << '\n';
			} else if (u < v) {
				int ans = 0;
				for (int b = $L - 1; b >= 0; b--) {
					if (rb[b][u + N] < v) {
						u = rb[b][u + N];
						ans |= (1 << b);
					}
				}
				cout << ans + 1 << '\n';
			} else if (u > v) {
				int ans = 0;
				for (int b = $L - 1; b >= 0; b--) {
					if (v < lb[b][u + N]) {
						u = lb[b][u + N];
						ans |= (1 << b);
					}
				}
				cout << ans + 1 << '\n';
			}
		}

	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:4: warning: ignoring '#pragma region debug' [-Wunknown-pragmas]
    4 | #pragma region debug
      | 
Main.cpp:198: warning: ignoring '#pragma endregion debug' [-Wunknown-pragmas]
  198 | #pragma endregion debug
      |

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13