結果

問題 No.2242 Cities and Teleporters
ユーザー wai4uwai4u
提出日時 2024-09-08 19:50:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 501 ms / 3,000 ms
コード長 10,874 bytes
コンパイル時間 3,245 ms
コンパイル使用メモリ 231,976 KB
実行使用メモリ 40,100 KB
最終ジャッジ日時 2024-09-08 19:50:38
合計ジャッジ時間 12,794 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 382 ms
39,964 KB
testcase_06 AC 333 ms
39,968 KB
testcase_07 AC 372 ms
39,968 KB
testcase_08 AC 501 ms
39,968 KB
testcase_09 AC 341 ms
39,972 KB
testcase_10 AC 181 ms
39,968 KB
testcase_11 AC 246 ms
39,820 KB
testcase_12 AC 262 ms
39,968 KB
testcase_13 AC 274 ms
40,100 KB
testcase_14 AC 336 ms
39,968 KB
testcase_15 AC 265 ms
39,968 KB
testcase_16 AC 338 ms
39,972 KB
testcase_17 AC 404 ms
39,968 KB
testcase_18 AC 240 ms
39,408 KB
testcase_19 AC 340 ms
39,264 KB
testcase_20 AC 265 ms
38,288 KB
testcase_21 AC 251 ms
38,564 KB
testcase_22 AC 264 ms
38,416 KB
testcase_23 AC 242 ms
39,968 KB
testcase_24 AC 223 ms
39,968 KB
testcase_25 AC 234 ms
39,968 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <set>
using namespace std;
#include <vector>
using std::vector;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
template <class T>
using vvvc = vc<vvc<T>>;
template <class T>
using vvvvc = vc<vvvc<T>>;
#define VC(T, a, ...) auto a = vector<T>(__VA_ARGS__)
#define VVC(T, a, n, ...) \
  auto a = vector(n, vector<T>(__VA_ARGS__));
#define VVVC(T, a, n, m, ...) \
  auto a = vector(n, vector(m, vector<T>(__VA_ARGS__)));
#define VVVVC(T, a, n, m, l, ...) \
  auto a = \
    vector(n, vector(m, vector(l, vector<T>(__VA_ARGS__))));
#define be begin()
#define en end()
#define all(a) (a).be, (a).en
#define rbe rbegin()
#define ren rend()
#define allr(a) a.rbe, a.ren
#include <algorithm>
using std::sort;
template<class A>
void sort(A& a) { sort(all(a)); }
#include <algorithm>
using std::sort;
template<class A>
void sortr(A& a) { sort(allr(a)); }
#include <algorithm>
using std::reverse;
template<class A>
void reverse(A& a) { reverse(all(a)); }
#define eval_0(a, ...) a
#define eval_1(a, b, ...) b
#define eval_2(a, b, c, ...) c
#define eval_3(a, b, c, d, ...) d
#define eval_4(a, b, c, d, e, ...) e
#define eval_5(a, b, c, d, e, f, ...) f
#define eval_6(a, b, c, d, e, f, g, ...) g
#define iter_1(a, A) for (auto&& a : A)
#define iter_2(a, b, A) for (auto&& [a, b] : A)
#define iter_3(a, b, c, A) for (auto&& [a, b, c] : A)
#define iter_4(a, b, c, d, A) for (auto&& [a, b, c, d] : A)
#define iter_5(a, b, c, d, e, A) \
  for (auto&& [a, b, c, d, e] : A)
#define iter(...) \
  eval_6(__VA_ARGS__, iter_5, iter_4, iter_3, iter_2, iter_1)( \
    __VA_ARGS__ \
  )
#define pb push_back
#define eb emplace_back
#define emp emplace
#include <numeric>
using std::accumulate;
template<class T, class U>
T sum(const vc<U>& a) { return accumulate(all(a), T(0)); }
#define loop while (1)
using ll = long long;
#define FOR_1(i, n) for (int i = 0; i < n; i++)
#define FOR_2(i, a, b) for (ll i = a; i < b; i++)
#define FOR_3(i, a, b, c) for (ll i = a; i < b; i += c)
#define FOR(...) \
  eval_4(__VA_ARGS__, FOR_3, FOR_2, FOR_1, rep)(__VA_ARGS__)
#define FORR_1(i, n) for (int i = n; i-- > 0;)
#define FORR_2(i, l, r) for (ll i = r; i-- > l;)
#define FORR_3(i, l, r, d) for (ll i = r - 1; i >= l; i -= c)
#define FORR(...) \
  eval_4(__VA_ARGS__, FORR_3, FORR_2, FORR_1)(__VA_ARGS__)
#define rep(t) for (int __ = 0; __ < t; ++__)
template <class T, class F>
T binary_search(F f, T ok, T ng) {
  while (abs(ok - ng) > 1) {
    T x = (ok + ng) / 2;
    (f(x) ? ok : ng) = x;
  }
  return ok;
}
#include <algorithm>
using std::lower_bound;
using std::upper_bound;
template<class A, class T>
auto lb(A& a, const T& x) { return lower_bound(all(a), x); }
template<class A, class T>
int lbi(const A& a, const T& x) { return lb(a, x) - a.be; }
template<class A, class T>
auto ub(A& a, const T& x) { return upper_bound(all(a), x); }
template<class A, class T>
int ubi(const A& a, const T& x) { return ub(a, x) - a.be; }
#include <string>
using std::string;
using str = string;
template<class A>
int len(const A& a) { return a.size(); }
#include <iostream>
using std::cout;
#define yesno(y, n) \
  void y(bool f = 1) { cout << (f ? #y : #n) << '\n'; } \
  void n(bool f = 1) { y(!f); }
yesno(yes, no);
yesno(Yes, No);
yesno(YES, NO);
template<class T=int>
vc<T> iota(int n, T v=0) {
  vc<T> a(n);
  iota(all(a), v);
  return a;
}
#include <utility>
using std::pair;
using pii = pair<int, int>;
#include <utility>
using std::pair;
using pll = pair<ll, ll>;
using vii = vc<pii>;
using vll = vc<pll>;
#define mt make_tuple
#define ins insert
template <class T, class U>
bool chmax(T& a, const U& b) { return b > a ? a = b, 1 : 0; }
template <class T, class U>
bool chmin(T& a, const U& b) { return b < a ? a = b, 1 : 0; }
using dbl = double;
using ld = long double;
#include <tuple>
using std::tuple;
template <class... T>
using tup = tuple<T...>;
#include <queue>
using std::priority_queue;
template<class T>
using max_que = priority_queue<T>;
using std::greater;
template<class T>
using min_que = priority_queue<T, vc<T>, greater<T>>;

template<class T>
T pop(min_que<T>& q) { T v = q.top(); q.pop(); return v; }
template<class T>
T pop(max_que<T>& q) { T v = q.top(); q.pop(); return v; }
#include <algorithm>
using std::max_element;
using std::min_element;
template <class A>
auto max(const A& a) { return *max_element(all(a)); }
template <class A>
auto min(const A& a) { return *min_element(all(a)); }
#define fi first
#define se second
#include <functional>
using std::function;
template <class F>
using fn = function<F>;
template <class A>
A fancy(const A& a, const vc<int>& p) {
  int n = len(p);
  A b(n);
  FOR(i, n) b[i] = a[p[i]];
  return b;
}
template <class A>
vc<int> argsort(const A& a) {
  auto p = iota(len(a));
  sort(all(p), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] < a[j];
  });
  return p;
}
vc<int> argperm(const vc<int>& p) {
  int n = len(p);
  vc<int> a(n);
  FOR(i, n) a[p[i]] = i;
  return a;
}
template <class A>
vc<int> rankify(const A& a) {
  return argperm(argsort(a));
}
/* deprecated
*/
#include <queue>
using std::queue;
template<class T>
T pop(queue<T>& q) {
  T x = q.front();
  q.pop();
  return x;
}

#include <queue>
using std::deque;
template <class T>
T pop_front(deque<T>& q) {
  T x = q.front();
  q.pop_front();
  return x;
}
template <class T>
T pop_back(deque<T>& q) {
  T x = q.back();
  q.pop_back();
  return x;
}
template <class T>
T pop(vc<T>& a) {
  T x = a.back();
  a.pop_back();
  return x;
}
class range {
  ll i, b, d;
public:
  range(ll a, ll b, ll d): i(a), b(b), d(d) {}
  range(ll a, ll b): range(a, b, a < b ? 1 : -1) {}
  range(int n): range(0, n) {}
  range& begin() { return *this; }
  range& end() { return *this; }
  range& operator++() {
    i += d;
    return *this;
  }
  bool operator!=(const range&) const {
    return d > 0 && i < b || d < 0 && i > b;
  }
  ll operator*() const { return i; }
};
template <class T>
int signum(T x) {
  return x > 0 ? 1 : x < 0 ? -1 : 0;
}
#include <random>
using std::mt19937_64;
using std::random_device;
mt19937_64 mrand(random_device{}());
int rng(int x) { return mrand() % x; }
template <class T>
T max(const set<T>& s) {
  return *s.rbe;
}
template <class T>
T min(const set<T>& s) {
  return *s.be;
}
template <class T>
T max(const multiset<T>& s) {
  return *s.rbe;
}
template <class T>
T min(const multiset<T>& s) {
  return *s.be;
}
constexpr double PI = acos(-1);
#include <iostream>
using namespace std;
void fastio() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}
template <class T, class U>
istream& operator>>(istream& i, pair<T, U>& p) {
  return i >> p.fi >> p.se;
}
#include <tuple>
#include <iostream>
using namespace std;
template <int k = 0, class T>
void scan_tup(istream& i, T& x) {
  if constexpr (tuple_size<T>::value > k) {
    i >> get<k>(x);
    scan_tup<k + 1>(i, x);
  }
}
template <class... T>
istream& operator>>(istream& i, tuple<T...>& x) {
  scan_tup(i, x);
  return i;
}
template <class I, class T>
I& operator>>(I& i, vc<T>& a) {
  iter(x, a) i >> x;
  return i;
}
#include <iostream>
using namespace std;
template <typename... T>
void scan(T&... a) { (cin >> ... >> a); }
#define VEC(T, a, n) VC(T, a, n); cin >> a;
#define V(T, a, n) VC(T, a, n); cin >> a;
#define VV(T, a, n, m) VVC(T, a, n, m); cin >> a;
#define VVV(T, a, n, m, l) VVC(T, a, n, m, l); cin >> a;
#define INT(...) int __VA_ARGS__; scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; scan(__VA_ARGS__)
#define DBL(...) dbl __VA_ARGS__; scan(__VA_ARGS__)
#define VI(a, n) V(int, a, n)
#define VL(a, n) V(ll, a, n)
#define VII(a, n) V(pii, a, n)
#define VLL(a, n) V(pll, a, n)
#define VSTR(a, n) V(str, a, n)
template <class T, size_t n>
ostream& operator<<(ostream& os, const array<T, n>& a) {
  FOR(i, n) {
    if (i) os << ' ';
    os << a[i];
  }
  return os;
}
template <class T, size_t n>
ostream& operator<<(ostream& os, array<array<T, n>, n> a) {
  FOR(i, n) os << a[i] << '\n';
  return os;
}
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& o, pair<T, U>& p) {
  return o << p.fi << ' ' << p.se;
}
#include <bits/stdc++.h>
using namespace std;
template <int k = 0, class T>
void out_tup(ostream& o, T& x) {
  if constexpr (tuple_size<T>::value > k) {
    if constexpr (k > 0) o << ' ';
    o << get<k>(x);
    out_tup<k + 1>(o, x);
  }
}
template <class... T>
ostream& operator<<(ostream& o, tuple<T...>& x) {
  out_tup(o, x);
  return o;
}
template <class O, class T>
O& operator<<(O& o, vc<T> a) {
  FOR(i, len(a)) {
    if (i) o << ' ';
    o << a[i];
  }
  return o;
}
template <class O, class T>
O& operator<<(O& o, vvc<T> a) {
  iter(x, a) o << x << '\n';
  return o;
}
#include <iostream>
using namespace std;
template <class T, class... U>
void print(T a, U... b) {
  cout << a;
  ((cout << ' ' << b), ...);
  cout << '\n';
}
template <class T, T (*op)(T, T), T (*e)()>
class doubling {
  vvc<int> f;
  vvc<T> x;
  int h;
public:
  doubling(const vc<int>& _f, const vc<T>& _x, int h = 60)
    : h(h) {
    int n = len(_f);
    assert(len(_x) == n);
    f.assign(h, vc<int>(n, -1));
    x.assign(h, vc<T>(n, e()));
    f[0] = _f;
    x[0] = _x;
    FOR(i, h - 1) FOR(j, n) {
      int k = f[i][j];
      if (k == -1) {
        f[i + 1][j] = -1;
        x[i + 1][j] = x[i][j];
        continue;
      }
      f[i + 1][j] = f[i][k];
      x[i + 1][j] = op(x[i][j], x[i][k]);
    }
  }
  pair<int, T> jump(int i, ll k) {
    assert(k >= 0);
    T y = e();
    int j = 0;
    while (k && i != -1) {
      if (k & 1) {
        y = op(y, x[j][i]);
        i = f[j][i];
      }
      k >>= 1;
      j++;
    }
    return {i, y};
  }
  template <class F>
  ll max_step(F g, int i) {
    T y = e();
    if (!g(i, y)) return -1;
    ll k = 0;
    FORR(j, h) {
      int ii = f[j][i];
      if (ii == -1) continue;
      T yy = op(y, x[j][i]);
      if (!g(ii, yy)) continue;
      k |= 1ll << j;
      i = ii;
      y = yy;
    }
    return k;
  }
};
int op(int x, int y) { return x + y; }
int e() { return 0; }
int main() {
  fastio();
  int n;
  cin >> n;
  vc<int> h(n), t(n);
  cin >> h >> t;
  auto p = argsort(h);
  auto pos = argperm(p);
  h = fancy(h, p);
  t = fancy(t, p);
  vc<int> f(n);
  int mx = -1;
  FOR(i, n) {
    chmax(mx, t[i]);
    f[i] = ubi(h, mx) - 1;
  }
  doubling<int, op, e> F(f, vc<int>(n, 1), 20);
  int q;
  cin >> q;
  auto query = [&](int u, int v) -> int {
    if (u == v) return 0;
    u = ubi(h, t[u]) - 1;
    if (v <= u) return 1;
    if (F.jump(u, n).fi < v) return -1;
    auto g = [&](int i, int x) -> bool {
      return i < v;
    };
    auto k = F.max_step(g, u);
    return 1 + k + 1;
  };
  rep(q) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    u = pos[u];
    v = pos[v];
    cout << query(u, v) << '\n';
  }
}
0