제출 #915376

#제출 시각아이디문제언어결과실행 시간메모리
915376EJIC_B_KEDAXRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
1858 ms69976 KiB
#ifdef LOCAL //#define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #include <random> #ifndef LOCAL //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt") #endif using namespace std; using ll = long long; using ld = long double; #define x first #define y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() template<typename T> struct segment_tree_default { std::vector<T> a{}; void (*mrg)(T&, const T&, const T&); size_t size{}; T e; segment_tree_default(int n, void (*merge)(T&, const T&, const T&), T neutral) { mrg = merge; e = neutral; size = 1; while (size < n) { size <<= 1; } a.resize(2 * size - 1, e); } segment_tree_default() = default; void update_element(int ind, const T& value) { ind += size - 1; a[ind] = value; while (ind) { ind = (ind - 1) / 2; mrg(a[ind], a[2 * ind + 1], a[2 * ind + 2]); } } void update_all(std::vector<T>& values) { while (size < values.size()) { size <<= 1; } a.resize(2 * size - 1); for (int i = size - 1; i < 2 * size - 1; i++) { if (i - size + 1 < values.size()) { a[i] = values[i - size + 1]; } else { a[i] = e; } } for (int i = size - 2; i >= 0; i--) { mrg(a[i], a[2 * i + 1], a[2 * i + 2]); } } T get(int l, int r, int l1 = 0, int r1 = -1, int i = 0) { if (r1 == -1) { r1 += size; } if (l1 >= l && r1 <= r) { return a[i]; } if (r1 < l || l1 > r) { return e; } T res; mrg(res, get(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2)); return res; } }; void mn(int& to, const int& a, const int& b) { to = min(a, b); } void mx(int& to, const int& a, const int& b) { to = max(a, b); } struct segment { int v, l, r; }; bool cmp (const segment& a, const segment& b) { if (a.l < b.l) { return true; } if (a.l > b.l) { return false; } return a.r < b.r; } bool operator < (const segment& a, const segment& b) { if (a.v < b.v) { return true; } if (a.v > b.v) { return false; } if (a.l < b.l) { return true; } if (a.l > b.l) { return false; } return a.r < b.r; } mt19937_64 mt(418); void solve(); void init(); int32_t main() { #ifndef LOCAL cin.tie(nullptr)->sync_with_stdio(false); #endif // srand(time(0)); init(); cout << fixed << setprecision(20); int t = 1; // cin >> t; while (t--) { solve(); } } const int N = 1 << 17, Q = 50500, M = 200200, LG = 17; segment_tree_default<int> stl[LG], str[LG]; int a[M], b[M], szl = 0, szr = 0; vector<int> start_l[N], start_r[N], end_l[N], end_r[N]; segment seg_l[M], seg_r[M]; set<segment> nwl, nwr; void init() { for (int i = 0; i < LG; i++) { stl[i] = segment_tree_default<int>(N, mn, INT32_MAX); str[i] = segment_tree_default<int>(N, mx, INT32_MIN); } } void solve() { int n, k, m; cin >> n >> k >> m; for (int i = 0; i < m; i++) { cin >> a[i] >> b[i]; a[i]--; b[i]--; } for (int i = 0; i < m; i++) { if (a[i] < b[i]) { start_r[a[i]].push_back(szr); end_r[min(b[i], a[i] + k - 1)].push_back(szr); seg_r[szr++] = {-b[i], a[i], min(b[i], a[i] + k - 1)}; } else { start_l[max(b[i], a[i] - k + 1)].push_back(szl); end_l[a[i]].push_back(szl); seg_l[szl++] = {b[i], max(b[i], a[i] - k + 1), a[i]}; } } nwl.insert({n, 0, 0}); nwr.insert({1, 0, 0}); for (int i = 0; i < n; i++) { for (int j : start_l[i]) { nwl.insert(seg_l[j]); } // cout << min((*nwl.begin()).v, i) << ' '; stl[0].update_element(i, min((*nwl.begin()).v, i)); for (int j : end_l[i]) { nwl.erase(seg_l[j]); } } // cout << '\n'; for (int i = 0; i < n; i++) { for (int j : start_r[i]) { nwr.insert(seg_r[j]); } // cout << max(-(*nwr.begin()).v, i) << ' '; str[0].update_element(i, max(-(*nwr.begin()).v, i)); for (int j : end_r[i]) { nwr.erase(seg_r[j]); } } // cout << '\n'; // assert(n <= 10000); for (int l = 1; l < LG; l++) { for (int i = 0; i < n; i++) { stl[l].update_element(i, stl[l - 1].get(stl[l - 1].a[N - 1 + i], str[l - 1].a[N - 1 + i])); str[l].update_element(i, str[l - 1].get(stl[l - 1].a[N - 1 + i], str[l - 1].a[N - 1 + i])); } } // assert(n <= 10000); int q; cin >> q; while (q--) { int l, r; cin >> l >> r; l--; r--; int nw = 0, left = l, right = l; for (int i = LG - 1; i >= 0; i--) { int new_l = stl[i].get(left, right), new_r = str[i].get(left, right); if (r > new_r || r < new_l) { left = new_l; right = new_r; nw += 1 << i; } } int new_l = stl[0].get(left, right), new_r = str[0].get(left, right); // cout << nw << ' ' << new_l << ' ' << new_r << '\n'; nw++; if (new_l <= r && r <= new_r) { cout << nw << '\n'; } else { cout << "-1\n"; } } }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In instantiation of 'segment_tree_default<T>::segment_tree_default(int, void (*)(T&, const T&, const T&), T) [with T = int]':
Main.cpp:143:60:   required from here
Main.cpp:31:21: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         while (size < n) {
      |                ~~~~~^~~
#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...