제출 #864219

#제출 시각아이디문제언어결과실행 시간메모리
864219prairie2022Railway Trip 2 (JOI22_ho_t4)C++17
100 / 100
298 ms257632 KiB
#include<bits/stdc++.h> typedef long long ll; #define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0); using namespace std; #pragma GCC optimize("Ofast") #define pii pair<int, int> #define F first #define S second inline pii operator+(pii p1, pii p2){ return {min(p1.F, p2.F), max(p1.S, p2.S)}; } vector<vector<vector<pii>>> table; // __lg(#train), __lg(range), range_left void build(int n, int k){ int m, a, b; vector<vector<int>> l(n+1), r(n+1); for(cin >> m; m; m--){ cin >> a >> b; if(a<b){ l[a].push_back(b); r[min(a+k-1, b-1)].push_back(b); } else{ l[max(a-k+1, b+1)].push_back(b); r[a].push_back(b); } } multiset<int> s; for(int i=1; i<=n; i++){ for(const int &st: l[i]) s.insert(st); if(!s.empty()) table[0][0][i] = {min(i, *s.begin()), max(i, *s.rbegin())}; else table[0][0][i] = {i, i}; for(const int &st: r[i]) s.erase(s.find(st)); } } inline pii get(int t, pii p){ p.S++; int tmp = __lg(p.S-p.F); return table[t][tmp][p.F]+table[t][tmp][p.S-(1<<tmp)]; } inline bool out(int t, pii p){ return p.F>t || t>p.S; } int main(){ fastio int n, k, y, q, s, t; cin >> n >> k; y = __lg(n)+1; table.assign(y+1, vector<vector<pii>>(y, vector<pii>(n+1))); build(n, k); // sprase table for(int t=0; t<=y; t++){ if(t){ for(int i=1; i<=n; i++) table[t][0][i] = get(t-1, table[t-1][0][i]); } for(int j=0; j<y-1; j++){ for(int i=1; i<=n-(1<<j); i++) table[t][j+1][i] = table[t][j][i]+table[t][j][i+(1<<j)]; } } // query for(cin >> q; q; q--){ cin >> s >> t; if(out(t, table[y][0][s])){ cout << "-1\n"; continue; } int ans = 0; pii cur = {s, s}; for(int tt=y-1; tt>-1; tt--){ pii tmp = get(tt, cur); if(out(t, tmp)){ ans ^= 1<<tt; cur = tmp; } } cout << ans+1 << '\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...