제출 #1263215

#제출 시각아이디문제언어결과실행 시간메모리
1263215miniobPassport (JOI23_passport)C++20
100 / 100
685 ms89924 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> prze; vector<pair<int, int>> graph[2*524300]; int odl[2*524300]; int sumk[2*524300]; int n; void dodajp(int l, int r, int curl, int curr, int cur, int jaki) { if(l > curr || r < curl) { return; } else if(l <= curl && curr <= r) { graph[cur].push_back({262143 + jaki, 1}); } else { dodajp(l, r, curl, (curl + curr) / 2, 2 * cur, jaki); dodajp(l, r, (curl + curr) / 2 + 1, curr, 2 * cur + 1, jaki); } } void djikstra(int skad) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; odl[skad] = 0; pq.push({0, skad}); for(int i = 1; i <= n; i++) { if(prze[i].first + 262143 <= skad && skad <= prze[i].second + 262143) { if(odl[262143 + i] > 0) { odl[262143 + i] = 0; pq.push({0, 262143 + i}); } } } while(!pq.empty()) { auto x = pq.top(); pq.pop(); if(odl[x.second] >= x.first) { for(auto t : graph[x.second]) { if(odl[t.first] > x.first + t.second) { odl[t.first] = x.first + t.second; pq.push({odl[t.first], t.first}); } } } } } int main() { cin >> n; for(int i = 2; i <= 524250; i++) { graph[i].push_back({i / 2, 0}); } prze.push_back({0, 0}); for(int i = 1; i <= n; i++) { int l, r; cin >> l >> r; prze.push_back({l, r}); dodajp(l, r, 1, 262144, 1, i); } for(int i = 0; i < 524290; i++) { odl[i] = 10000000; } djikstra(262144); for(int i = 0; i < 524290; i++) { sumk[i] += odl[i]; odl[i] = 10000000; } djikstra(262143 + n); for(int i = 0; i < 524290; i++) { sumk[i] += odl[i]; odl[i] = 10000000; } for(int i = 262144; i < 262144 + n; i++) { graph[0].push_back({i, min(sumk[i], 10000000)}); } djikstra(0); int q; cin >> q; while(q--) { int x; cin >> x; if(odl[262143 + x] >= 10000000) { cout << -1 << endl; } else { cout << odl[262143 + x] + 1 << endl; } } 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...