Submission #1264794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264794		kustov_vadim_533	Railway Trip 2 (JOI22_ho_t4)	C++20	8 / 100	2096 ms	7340 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

const int LGN = 17;
const int N = 1 << LGN;

pair<int, int> tree[LGN][N << 1];

struct event{
	int i, tp;
	event(int i, int tp) : i(i), tp(tp){}
};

void solve() {
	int n, k, m;
	cin >> n >> k >> m;

	vector<event> evs;

	for (int i = 0; i < m; ++i){
		int x, y;
		cin >> x >> y;

		--x, --y;

		if (x < y){
			evs.emplace_back(x, y + 1);
			evs.emplace_back(min(x + k - 1, y), -y - 1);
		}
		else{
			evs.emplace_back(max(y, x - k + 1), y + 1);
			evs.emplace_back(x, -y - 1);
		}
	}

	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; ++i){
		evs.emplace_back(i, 0);
		a[i] = {i, i};

	}

	sort(evs.begin(), evs.end(), [&](event x, event y){
		if (x.i != y.i) return x.i < y.i;
		return x.tp > y.tp;
	});

	multiset<int> s;
	for (event ev : evs){
		if (ev.tp == 0){
			if (!s.empty()){
				a[ev.i].first = min(a[ev.i].first, *s.begin());
				a[ev.i].second = max(a[ev.i].second, *(--s.end()));
			}
		}
		else if (ev.tp > 0){
			s.insert(ev.tp - 1);
		}
		else{
			s.erase(s.find(-(ev.tp + 1)));
		}
	}

	int q;
	cin >> q;

	for (int i = 0; i < q; ++i){
		int x, y;
		cin >> x >> y;

		--x, --y;

		int l = x, r = x;
		bool fl = false;
		for (int j = 0; j <= m; ++j){
			if (l <= y && y <= r){
				cout << j << '\n';
				fl = true;
				break;
			}
			int nl = x, nr = x;
			for (int f = l; f <= r; ++f){
				nl = min(nl, a[f].first);
				nr = max(nr, a[f].second);
			}
			l = nl;
			r = nr;
		}

		if (!fl) {
			cout << "-1\n";
		}
	}

}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

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