Submission #899655

#TimeUsernameProblemLanguageResultExecution timeMemory
899655MilosMilutinovicRailway Trip 2 (JOI22_ho_t4)C++14
100 / 100
1639 ms523848 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; int m; cin >> m; vector<vector<vector<int>>> qs(n, vector<vector<int>>(2)); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; --a; --b; if (a < b) { qs[a][0].push_back(b); qs[min(b, a + k - 1)][0].push_back(~b); } else { qs[max(b, a - k + 1)][1].push_back(b); qs[a][1].push_back(~b); } } const int LOG = 20; vector<vector<int>> R(n, vector<int>(LOG)); vector<vector<int>> L(n, vector<int>(LOG)); vector<multiset<int>> st(2); for (int i = 0; i < n; i++) { for (int t = 0; t < 2; t++) { for (int x : qs[i][t]) { if (x >= 0) { st[t].insert(x); } } } R[i][0] = (st[0].empty() ? i : *prev(st[0].end())); L[i][0] = (st[1].empty() ? i : *st[1].begin()); for (int t = 0; t < 2; t++) { for (int x : qs[i][t]) { if (x < 0) { x = ~x; st[t].erase(st[t].find(x)); } } } } for (int j = 1; j < LOG; j++) { vector<vector<int>> mn(n, vector<int>(LOG)); vector<vector<int>> mx(n, vector<int>(LOG)); vector<int> logs(n + 1); for (int i = 0; i < n; i++) { mn[i][0] = L[i][j - 1]; mx[i][0] = R[i][j - 1]; } for (int l = 1; l < LOG; l++) { for (int i = 0; i + (1 << l) <= n; i++) { mn[i][l] = min(mn[i][l - 1], mn[i + (1 << (l - 1))][l - 1]); mx[i][l] = max(mx[i][l - 1], mx[i + (1 << (l - 1))][l - 1]); } } for (int i = 2; i <= n; i++) { logs[i] = logs[i >> 1] + 1; } auto QueryMin = [&](int l, int r) { int k = logs[r - l + 1]; return min(mn[l][k], mn[r - (1 << k) + 1][k]); }; auto QueryMax = [&](int l, int r) { int k = logs[r - l + 1]; return max(mx[l][k], mx[r - (1 << k) + 1][k]); }; for (int i = 0; i < n; i++) { L[i][j] = QueryMin(L[i][j - 1], R[i][j - 1]); R[i][j] = QueryMax(L[i][j - 1], R[i][j - 1]); } } vector<vector<vector<int>>> mn(LOG, vector<vector<int>>(n, vector<int>(LOG))); vector<vector<vector<int>>> mx(LOG, vector<vector<int>>(n, vector<int>(LOG))); vector<int> logs(n + 1); for (int i = 2; i <= n; i++) { logs[i] = logs[i >> 1] + 1; } for (int l = 0; l < LOG; l++) { for (int i = 0; i < n; i++) { mn[l][i][0] = L[i][l]; mx[l][i][0] = R[i][l]; } for (int j = 1; j < LOG; j++) { for (int i = 0; i + (1 << j) <= n; i++) { mn[l][i][j] = min(mn[l][i][j - 1], mn[l][i + (1 << (j - 1))][j - 1]); mx[l][i][j] = max(mx[l][i][j - 1], mx[l][i + (1 << (j - 1))][j - 1]); } } } auto QueryMin = [&](int i, int l, int r) { int k = logs[r - l + 1]; return min(mn[i][l][k], mn[i][r - (1 << k) + 1][k]); }; auto QueryMax = [&](int i, int l, int r) { int k = logs[r - l + 1]; return max(mx[i][l][k], mx[i][r - (1 << k) + 1][k]); }; int q; cin >> q; while (q--) { int a, b; cin >> a >> b; --a; --b; if (L[a][LOG - 1] > b || R[a][LOG - 1] < b) { cout << -1 << '\n'; continue; } int cl = a, cr = a; int res = 1; for (int i = LOG - 1; i >= 0; i--) { if (QueryMin(i, cl, cr) <= b && QueryMax(i, cl, cr) >= b) { continue; } res += (1 << i); int new_cl = QueryMin(i, cl, cr); int new_cr = QueryMax(i, cl, cr); cl = new_cl; cr = new_cr; } cout << res << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...