제출 #751379

#제출 시각아이디문제언어결과실행 시간메모리
751379KihihihiRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
710 ms119592 KiB
#include <iostream> #include <iomanip> #include <algorithm> #include <numeric> #include <cmath> #include <cassert> #include <ctime> #include <chrono> #include <cstdio> #include <random> #include <vector> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <deque> #include <queue> #include <bitset> #include <list> #include <fstream> #include <functional> #include <complex> using namespace std; mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); short skip_cin = 0; const long long INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18; const long double EPS = 1e-9, PI = acos(-1); struct quemin { deque<pair<long long, long long>> d; long long l, r; quemin() { l = 0; r = -1; } void push_back(long long val) { r++; while (d.size() && d.back().first >= val) { d.pop_back(); } d.push_back({ val, r }); } void pop_front() { if (d.front().second == l) { d.pop_front(); } l++; } long long get_min() { return d.front().first; } }; struct quemax { deque<pair<long long, long long>> d; long long l, r; quemax() { l = 0; r = -1; } void push_back(long long val) { r++; while (d.size() && d.back().first <= val) { d.pop_back(); } d.push_back({ val, r }); } void pop_front() { if (d.front().second == l) { d.pop_front(); } l++; } long long get_max() { return d.front().first; } }; struct segtree { long long n; vector<pair<long long, long long>> t; segtree() {} segtree(vector<pair<long long, long long>>& in) { n = in.size(); t.resize(n * 4); build(0, 0, n - 1, in); } void build(long long v, long long tl, long long tr, vector<pair<long long, long long>>& in) { if (tl == tr) { t[v] = in[tl]; return; } long long tm = (tl + tr) / 2; build(v * 2 + 1, tl, tm, in); build(v * 2 + 2, tm + 1, tr, in); t[v].first = min(t[v * 2 + 1].first, t[v * 2 + 2].first); t[v].second = max(t[v * 2 + 1].second, t[v * 2 + 2].second); } pair<long long, long long> get_seg(long long v, long long tl, long long tr, long long l, long long r) { if (tr < l || r < tl) { return { INF, -INF }; } if (l <= tl && tr <= r) { return t[v]; } long long tm = (tl + tr) / 2; auto [l1, r1] = get_seg(v * 2 + 1, tl, tm, l, r); auto [l2, r2] = get_seg(v * 2 + 2, tm + 1, tr, l, r); return { min(l1, l2), max(r1, r2) }; } pair<long long, long long> get(long long l, long long r) { return get_seg(0, 0, n - 1, l, r); } }; void solve() { long long n, k, m; vector<long long> tol, tor; cin >> n >> k >> m; tol.resize(n, INF); tor.resize(n, -INF); for (long long i = 0; i < m; i++) { long long a, b; cin >> a >> b; a--; b--; if (a < b) { tor[a] = max(tor[a], b); } else { tol[a] = min(tol[a], b); } } quemax qmx; quemin qmn; for (long long i = 0; i < k; i++) { qmn.push_back(tol[i]); } vector<pair<long long, long long>> sg(n); for (long long i = 0; i < n; i++) { qmx.push_back(tor[i]); if (i - k >= 0) { qmx.pop_front(); } if (i > 0) { qmn.pop_front(); if (i + k - 1 < n) { qmn.push_back(tol[i + k - 1]); } } sg[i].first = min(qmn.get_min(), i); sg[i].second = max(qmx.get_max(), i); } vector<segtree> sgtbin(LOG); sgtbin[0] = segtree(sg); for (long long i = 1; i < LOG; i++) { for (long long j = 0; j < n; j++) { sg[j] = sgtbin[i - 1].get(sg[j].first, sg[j].second); } sgtbin[i] = segtree(sg); } long long q; cin >> q; while (q--) { long long a, b; cin >> a >> b; a--; b--; if (a == b) { cout << 0 << "\n"; continue; } auto [finl, finr] = sgtbin.back().get(a, a); if (b < finl || finr < b) { cout << -1 << "\n"; continue; } long long left = a, right = a; long long ans = 1; for (long long i = LOG - 1; i > -1; i--) { auto [cl, cr] = sgtbin[i].get(left, right); if (cl <= b && b <= cr) { continue; } ans += (1ll << i); left = cl; right = cr; } cout << ans << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); srand(time(NULL)); int tst = 1; //cin >> tst; while (tst--) { solve(); } return 0; } /* <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀ ⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀ ⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀ ⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀ ⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇ ⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇ ⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁ ⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀ ⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀ ⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀ ⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀ ⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀ ⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀ ⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀ ⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀ ⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀ ⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧ ⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘ ⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀ ⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀ <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 */
#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...