Submission #887093

#TimeUsernameProblemLanguageResultExecution timeMemory
887093VerdantGMDRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
794 ms36560 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; int n, k; int maxs[200003]; int mins[200003]; int minjp[200003][20]; int maxjp[200003][20]; int base = n + 1; void updmax(int a, int b, int x) { a += base - 1; b += base + 1; while(a/2 != b/2) { if(a % 2 == 0) { maxs[a+1] = max(x, maxs[a+1]); } if(b % 2 == 1) { maxs[b-1] = max(x, maxs[b-1]); } a/=2; b/=2; } } void updmin(int a, int b, int x) { a += base - 1; b += base + 1; while(a/2 != b/2) { if(a % 2 == 0) { if(mins[a+1] != 0) { mins[a+1] = min(x, mins[a+1]); } else { mins[a+1] = x; } } if(b % 2 == 1) { if(mins[b-1] != 0) { mins[b-1] = min(x, mins[b-1]); } else { mins[b-1] = x; } } a/=2; b/=2; } } int querymin(int a) { a += base; int minn = 1e9; while(a != 0) { if(mins[a] != 0) { minn = min(mins[a], minn); } a/=2; } return minn; } int querymax(int a) { a += base; int maxx = -1e9; while(a != 0) { if(maxs[a] != 0) { maxx = max(maxs[a], maxx); } a/=2; } return maxx; } void updmaxjp(int a, int it, int val) { a += base; while(a != 0) { if(maxjp[a][it] != 0) { maxjp[a][it] = max(val, maxjp[a][it]); } else { maxjp[a][it] = val; } a/=2; } } void updminjp(int a, int it, int val) { a += base; while(a != 0) { if(minjp[a][it] != 0) { minjp[a][it] = min(val, minjp[a][it]); } else { minjp[a][it] = val; } a/=2; } } int querymaxjp(int a, int b, int it) { a += base - 1; b += base + 1; int maxx = -1e9; while(a/2 != b/2) { if(a % 2 == 0) { if(maxjp[a+1][it] != 0) { maxx = max(maxx, maxjp[a+1][it]); } } if(b % 2 == 1) { if(maxjp[b-1][it] != 0) { maxx = max(maxx, maxjp[b-1][it]); } } a/=2; b/=2; } return maxx; } int queryminjp(int a, int b, int it) { a += base - 1; b += base + 1; int minn = 1e9; while(a/2 != b/2) { if(a % 2 == 0) { if(minjp[a+1][it] != 0) { minn = min(minn, minjp[a+1][it]); } } if(b % 2 == 1) { if(minjp[b-1][it] != 0) { minn = min(minn, minjp[b-1][it]); } } a/=2; b/=2; } return minn; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; int m; cin >> m; base = n + 1; for(int i = base; i <= base + n; i++) { mins[i] = i - base; maxs[i] = i - base; } for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; if(a < b) { updmax(a, min(a + k-1, b), b); } else { updmin(max(a - k+1, b), a, b); } } for(int i = 1; i <= n; i++) { updminjp(i, 0, querymin(i)); updmaxjp(i, 0, querymax(i)); //cout << i << " " << minjp[i+base][0] << " " << maxjp[i+base][0] << endl; } //cout << endl; for(int it = 1; it < 20; it++) { for (int i = 1; i <= n; i++) { updmaxjp(i, it, querymaxjp(minjp[i + base][it - 1], maxjp[i + base][it - 1], it - 1)); updminjp(i, it, queryminjp(minjp[i + base][it - 1], maxjp[i + base][it - 1], it - 1)); //cout << i << " " << minjp[i+base][it] << " " << maxjp[i+base][it] << endl; } //cout << endl; } cin >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; if(a == b) { cout << 0 << endl; continue; } if(a < b) { int wyn = 0; int curl = a; int curr = a; for(int it = 19; it >= 0; it--) { if(querymaxjp(curl, curr, it) < b) { wyn += pow(2, it); int temp = queryminjp(curl, curr, it); curr = querymaxjp(curl, curr, it); curl = temp; } } if(querymaxjp(curl, curr, 0) >= b) { cout << wyn + 1 << endl; } else { cout << -1 << endl; } } else if(a > b) { int wyn = 0; int curl = a; int curr = a; for(int it = 19; it >= 0; it--) { if(queryminjp(curl, curr, it) > b) { wyn += pow(2, it); int temp = queryminjp(curl, curr, it); curr = querymaxjp(curl, curr, it); curl = temp; } } if(queryminjp(curl, curr, 0) <= b) { cout << wyn + 1 << endl; } else { cout << -1 << endl; } } } }
#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...