oj.uz

Submission #724159

# Submission time Handle Problem Language Result Execution time Memory
724159 2023-04-14T18:48:10 Z 42kangaroo Railway Trip 2 (JOI22_ho_t4) C++17
16 / 100
 339 ms 524288 KB 
//
// Created by 42kangaroo on 16/03/2023.
//
#include "bits/stdc++.h"

using namespace std;

#define int long long

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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1240 KB Output is correct
2 Correct 1 ms 1220 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1296 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 2 ms 1316 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1240 KB Output is correct
2 Correct 1 ms 1220 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1296 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 2 ms 1316 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 6 ms 9548 KB Output is correct
14 Correct 8 ms 9556 KB Output is correct
15 Correct 6 ms 9556 KB Output is correct
16 Correct 7 ms 9556 KB Output is correct
17 Correct 6 ms 9556 KB Output is correct
18 Correct 6 ms 9556 KB Output is correct
19 Correct 6 ms 9044 KB Output is correct
20 Correct 6 ms 9548 KB Output is correct
21 Correct 7 ms 9552 KB Output is correct
22 Correct 6 ms 9556 KB Output is correct
23 Correct 7 ms 9576 KB Output is correct
24 Correct 7 ms 9556 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 294 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 312 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 339 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1240 KB Output is correct
2 Correct 1 ms 1220 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1296 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 2 ms 1316 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 6 ms 9548 KB Output is correct
14 Correct 8 ms 9556 KB Output is correct
15 Correct 6 ms 9556 KB Output is correct
16 Correct 7 ms 9556 KB Output is correct
17 Correct 6 ms 9556 KB Output is correct
18 Correct 6 ms 9556 KB Output is correct
19 Correct 6 ms 9044 KB Output is correct
20 Correct 6 ms 9548 KB Output is correct
21 Correct 7 ms 9552 KB Output is correct
22 Correct 6 ms 9556 KB Output is correct
23 Correct 7 ms 9576 KB Output is correct
24 Correct 7 ms 9556 KB Output is correct
25 Runtime error 294 ms 524288 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -