제출 #676839

#제출 시각아이디문제언어결과실행 시간메모리
676839abysmalRailway Trip 2 (JOI22_ho_t4)C++14
27 / 100
2093 ms60488 KiB
#include<iostream> #include<stdio.h> #include<stdint.h> #include<vector> #include<algorithm> #include<utility> #include<set> #include<map> #include<queue> #include<stack> #include<deque> #include<string> using namespace std; const int64_t INF = (int64_t) 4 * 1e5 + 5; const int64_t mINF = 18; const int64_t MOD = (int64_t) 1e9 + 7; const int nbit = 11; const int ndig = 10; const int nchar = 26; const int p1 = 31; const int p2 = 53; const int D = 4; int dr[D] = {0, 1, 0, -1}; int dc[D] = {1, 0, -1, 0}; // 0 right // 1 down // 2 left // 3 up struct Solution { int n; int k; int m; int sz; int LOG; vector<vector<int> > a; vector<vector<int> > b; vector<vector<int> > treer; vector<vector<int> > treel; vector<vector<pair<int, int> > > range; Solution() {} void solve() { cin >> n >> k >> m; a.resize(n); b.resize(n); for(int i = 0; i < m; i++) { int u; int v; cin >> u >> v; u--; v--; if(u < v) a[u].push_back(v); else b[u].push_back(v); } buildTree(); int q; cin >> q; for(int i = 0; i < q; i++) { int s; int t; cin >> s >> t; s--; t--; int l = 1; int r = n; int ans = -1; while(l <= r) { int mid = l + (r - l) / 2; if(check(mid, s, t)) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans << "\n"; } } bool check(int dis, int& s, int& t) { int l = s; int r = s; while(dis != 0) { int bt = 31 - __builtin_clz(dis); int newl = get(1, 0, sz - 1, l, r, bt, 0); int newr = get(1, 0, sz - 1, l, r, bt, 1); l = newl; r = newr; dis ^= MASK(bt); } return (l <= t && t <= r); } void buildTree() { sz = n; LOG = 0; while(MASK(LOG) <= n) LOG++; while(__builtin_popcount(sz) != 1) sz++; treer.resize(LOG, vector<int>(sz * 2, -1)); treel.resize(LOG, vector<int>(sz * 2, n)); range.resize(LOG, vector<pair<int, int> >(n, make_pair(-1, -1))); for(int i = 0; i < n; i++) { range[0][i] = make_pair(i, i); } deque<pair<int, int> > dq; for(int i = 0; i < n; i++) { for(int j = 0; j < (int) a[i].size(); j++) { int v = a[i][j]; while(!dq.empty() && dq.back().second <= v) dq.pop_back(); dq.push_back(make_pair(i, v)); } while(!dq.empty() && (dq.front().first + k - 1 < i || dq.front().second < i)) dq.pop_front(); if(dq.empty()) continue; range[0][i].second = dq.front().second; } deque<pair<int, int> > dq2; for(int i = n - 1; i >= 0; i--) { for(int j = 0; j < (int) b[i].size(); j++) { int v = b[i][j]; while(!dq2.empty() && dq2.back().second >= v) dq2.pop_back(); dq2.push_back(make_pair(i, v)); } while(!dq2.empty() && (dq2.front().first - k + 1 > i || dq2.front().second > i)) dq2.pop_front(); if(dq2.empty()) continue; range[0][i].first = dq2.front().second; } for(int i = 0; i < n; i++) { treel[0][sz + i] = range[0][i].first; treer[0][sz + i] = range[0][i].second; } for(int i = sz - 1; i >= 1; i--) { treer[0][i] = max(treer[0][i * 2], treer[0][i * 2 + 1]); treel[0][i] = min(treel[0][i * 2], treel[0][i * 2 + 1]); } for(int i = 1; i < LOG; i++) { // cerr << "i = " << i << "\n"; int prev = i - 1; for(int j = 0; j < n; j++) { int l = range[i - 1][j].first; int r = range[i - 1][j].second; int newl = get(1, 0, sz - 1, l, r, prev, 0); int newr = get(1, 0, sz - 1, l, r, prev, 1); // cerr << "l = " << l << " ; r = " << r << "\n"; // cerr << "newl = " << newl << " ; newr = " << newr << "\n"; update(j, i, newl, 0); update(j, i, newr, 1); range[i][j] = make_pair(newl, newr); } // cerr << "\n"; } } void update(int& id, int& d, int& val, int t) { if(t == 0) treel[d][sz + id] = min(treel[d][sz + id], val); else treer[d][sz + id] = max(treer[d][sz + id], val); for(int i = (sz + id) / 2; i >= 1; i /= 2) { if(t == 0) treel[d][i] = min(treel[d][i * 2], treel[d][i * 2 + 1]); else treer[d][i] = max(treer[d][i * 2], treer[d][i * 2 + 1]); } } int get(int node, int nleft, int nright, int& left, int& right, int& d, int t) { if(left <= nleft && nright <= right) { if(t == 0) return treel[d][node]; return treer[d][node]; } if(nleft > right || nright < left) { if(t == 0) return n; return -1; } int mid = nleft + (nright - nleft) / 2; int t1 = get(node * 2, nleft, mid, left, right, d, t); int t2 = get(node * 2 + 1, mid + 1, nright, left, right, d, t); if(t == 0) return min(t1, t2); return max(t1, t2); } int modsub(int t1, int t2) { int res = t1 - t2; if(res < 0) res += MOD; return res; } int modadd(int t1, int t2) { int res = t1 + t2; if(res >= MOD) res -= MOD; return res; } int modmul(int t1, int t2) { int64_t res = 1LL * t1 * t2; return (res % MOD); } bool BIT(int& mask, int& j) { return (mask & MASK(j)); } int64_t MASK(int64_t j) { return (1LL << j); } }; void __startup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); } int main() { __startup(); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { Solution().solve(); } 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...