Advertisement
limagination

5

Feb 2nd, 2022
1,204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2.  
  3. #define endl "\n"
  4. using namespace std;
  5. using pii = pair<int, int>;
  6.  
  7. void solve() {
  8.   int n;
  9.   cin >> n;
  10.   vector<int> a(n);
  11.   vector<int> b(n);
  12.   for (int& v: a)
  13.     cin >> v;
  14.   for (int& v: b)
  15.     cin >> v;
  16.   queue<pii> q;
  17.   q.emplace(0, 0);
  18.   set<int> used;
  19.   for (int i = 1; i <= n; ++i)
  20.     used.insert(i);
  21.   vector<int> ans(n + 1, -1);
  22.   ans[0] = 0;
  23.   while(q.size()) {
  24.     auto [num, cur] = q.front();
  25.     q.pop();
  26.     if (cur == n) {
  27.       break;
  28.     }
  29.     for (auto it = used.lower_bound(cur); it != used.end() && *it <= cur + a[n - cur - 1]; it = used.erase(it)) {
  30.       int new_height = *it;
  31.       if (ans[new_height - b[n - new_height - 1]] == -1) {
  32.         ans[new_height - b[n - new_height - 1]] = num + 1;
  33.         q.emplace(num + 1, new_height - b[n - new_height - 1]);
  34.       }
  35.     }
  36.   }
  37.   cout << ans[n] << endl;
  38. }
  39.  
  40. int main() {
  41.   ios::sync_with_stdio(false);
  42.   cin.tie(nullptr);
  43.   cout.tie(nullptr);
  44.   int tests = 1;
  45.   //cin >> tests;
  46.   while(tests--) {
  47.     //auto start = chrono::high_resolution_clock::now();
  48.       solve();
  49.     // auto end = chrono::high_resolution_clock::now();
  50.     // cout << endl << (chrono::duration_cast<chrono::duration<double>>(end - start)).count();
  51.   }
  52.   return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement