Submission #724160

#	Time	Username	Problem	Language	Result	Execution time	Memory
724160		42kangaroo	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	460 ms	523272 KiB

Main

//
// Created by 42kangaroo on 16/03/2023.
//
#include "bits/stdc++.h"

using namespace std;

template<typename T>
using g_t = vector<vector<T>>;

vector<int> logt;
vector<int> p2;

struct Train {
	int last, en;
};

struct BinJu {
	g_t<int> forWBinJ;
	g_t<vector<int>> spTForw;
	g_t<int> baWBinJ;
	g_t<vector<int>> spTBa;
};

vector<int> makeMaxDist(g_t<Train> &ne, bool forw) {
	vector<int> nex(ne.size());
	std::iota(nex.begin(), nex.end(), 0);
	auto comp = [&](const Train &l, const Train &r) { return (forw ? l.en < r.en : l.en > r.en); };
	priority_queue<Train, vector<Train>, decltype(comp)> p(comp);
	for (int i = (forw ? 0 : (int) ne.size() - 1); (forw ? i < ne.size() : i >= 0); (forw ? ++i : --i)) {
		for (auto &t: ne[i]) {
			p.push(t);
		}
		while (!p.empty() && (forw ? p.top().last < i : p.top().last > i)) p.pop();
		if (!p.empty()) nex[i] = p.top().en;
	}
	return nex;
}

void logT(int n) {
	logt = vector<int>(n + 1, 0);
	for (int i = 2; i <= n; ++i) {
		logt[i] = logt[i / 2] + 1;
	}
}

g_t<int> sparseT(vector<int> &vals, bool ma) {
	g_t<int> spT(logt[vals.size()] + 1, vector<int>(vals.size()));
	spT[0] = vals;
	for (int i = 1; i < spT.size(); ++i) {
		for (int j = 0; j < spT[i].size() - p2[i] + 1; ++j) {
			spT[i][j] = ma ? max(spT[i - 1][j], spT[i - 1][j + p2[i - 1]]) :
			            min(spT[i - 1][j], spT[i - 1][j + p2[i - 1]]);
		}
	}
	return spT;
}

int mi(int a, int b, g_t<int> &spT, bool ma) {
	return ma ? max(spT[logt[b - a + 1]][a], spT[logt[b - a + 1]][b - p2[logt[b - a + 1]] + 1]) :
	       min(spT[logt[b - a + 1]][a], spT[logt[b - a + 1]][b - p2[logt[b - a + 1]] + 1]);
}

BinJu binJ(vector<int> &forw, vector<int> &back) {
	g_t<int> forWBinJ(logt[forw.size()] + 2, vector<int>(forw.size(), 0));
	g_t<vector<int>> spTForw(logt[forw.size()] + 2);
	g_t<int> baWBinJ(logt[forw.size()] + 2, vector<int>(forw.size(), 0));
	g_t<vector<int>> spTBa(logt[forw.size()] + 2);
	forWBinJ[0] = forw;
	baWBinJ[0] = back;
	spTForw[0] = sparseT(forw, true);
	spTBa[0] = sparseT(back, false);
	for (int i = 1; i < forWBinJ.size(); ++i) {
		for (int j = 0; j < forw.size(); ++j) {
			forWBinJ[i][j] = mi(baWBinJ[i - 1][j], forWBinJ[i - 1][j], spTForw[i - 1], true);
			baWBinJ[i][j] = mi(baWBinJ[i - 1][j], forWBinJ[i - 1][j], spTBa[i - 1], false);
		}
		spTForw[i] = sparseT(forWBinJ[i], true);
		spTBa[i] = sparseT(baWBinJ[i], false);
	}
	return {forWBinJ, spTForw, baWBinJ, spTBa};
}

int co(int a, int b, BinJu& binJ) {
	if (a == b) return 0;
	int actF=a, actB=a;
	int ans = 1;
	for (int i = binJ.baWBinJ.size() - 1; i >= 0; --i) {
		int nF = mi(actB, actF, binJ.spTForw[i], true);
		int nB = mi(actB, actF, binJ.spTBa[i], false);
		if (a < b && nF < b) {
			actF = nF;actB = nB;
			ans += p2[i];
		} else if (a > b && nB > b) {
			actF = nF;actB = nB;
			ans += p2[i];
		}
	}
	return ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, r;
	cin >> n >> r >> m;
	logT(n);
	for (int i = 1; i < 2*n; i <<= 1) {
		p2.push_back(i);
	}
	g_t<Train> forw(n), backw(n);
	for (int i = 0; i < m; ++i) {
		int s, e;
		cin >> s >> e;
		--s;
		--e;
		if (s < e) {
			forw[s].push_back({min(s + r - 1, e), e});
		} else {
			backw[s].push_back({max(s - r + 1, e), e});
		}
	}
	vector<int> neFo = makeMaxDist(forw, true), neBa = makeMaxDist(backw, false);
	auto BinJ = binJ(neFo, neBa);
	int q;
	cin >> q;
	while(q--) {
		int s, t;
		cin >> s >> t;
		--s;--t;
		int ans = co(s, t, BinJ);
		if (ans > n) cout << "-1\n";
		else cout << ans << "\n";
	}
}
/*20 5
10
1 9
3 12
8 18
14 18
15 20
9 1
12 3
18 8
18 14
20 15*/

Compilation message (stderr)

Main.cpp: In function 'std::vector<int> makeMaxDist(g_t<Train>&, bool)':
Main.cpp:30:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Train, std::allocator<Train> >, std::allocator<std::vector<Train, std::allocator<Train> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = (forw ? 0 : (int) ne.size() - 1); (forw ? i < ne.size() : i >= 0); (forw ? ++i : --i)) {
      |                                                         ~~^~~~~~~~~~~
Main.cpp: In function 'g_t<int> sparseT(std::vector<int>&, bool)':
Main.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int>, std::allocator<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 1; i < spT.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
Main.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int j = 0; j < spT[i].size() - p2[i] + 1; ++j) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'BinJu binJ(std::vector<int>&, std::vector<int>&)':
Main.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int>, std::allocator<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 1; i < forWBinJ.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~~~
Main.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int j = 0; j < forw.size(); ++j) {
      |                   ~~^~~~~~~~~~~~~

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