Submission #31537793

---

Source Code Expand

#include <bits/stdc++.h>
#define sz(c) int(c.size())
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = (b)-1; i >= (a); --i)
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <local/debug.h>
#else
#define debug(...) (void)0
#endif

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;
  vector<int> a(n), b(n);
  rep(i, 0, n) cin >> a[i];
  rep(i, 0, n) cin >> b[i];

  map<int, int> s;
  array<int, 4> cnt{};

  auto add = [&](int x, int y) {
    int pre = s[x];
    int cur = pre | y;
    if (cur != pre) {
      cnt[pre]--;
      cnt[cur]++;
      s[x] = cur;
    }
  };

  int p = 0, q = 0;
  add(a[p++], 1);
  add(b[q++], 2);

  vector<pair<pair<int, int>, pair<int, int>>> seg;
  while (true) {
    if (cnt[1] + cnt[2] == 0) {
      int p1 = p, q1 = q;
      while (p < n && s.count(a[p]))
        p++;
      while (q < n && s.count(b[q]))
        q++;
      seg.emplace_back(make_pair(p1, p), make_pair(q1, q));
      if (p == n && q == n)
        break;
      if (p < n)
        add(a[p++], 1);
      if (q < n)
        add(b[q++], 2);
      continue;
    }

    if (cnt[1] != 0) {
      if (q == n)
        break;
      add(b[q++], 2);
      continue;
    }

    assert(cnt[2] != 0);
    if (p == n)
      break;
    add(a[p++], 1);
  }

  using pii = pair<int, int>;
  map<int, pair<pii, pii>> f;
  for (auto it : seg)
    f[it.first.first] = it;

  int Q;
  cin >> Q;
  while (Q--) {
    int x, y;
    cin >> x >> y;

    auto check = [&]() {
      auto it = f.upper_bound(x);
      if (it == f.begin())
        return false;
      it--;
      auto [p1, p2] = it->second;
      assert(p1.first <= x);
      return x <= p1.second && p2.first <= y && y <= p2.second;
    };

    cout << (check() ? "Yes" : "No") << '\n';
  }
}

Submission Info

Judge Result