TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Prefix Equality

問題

E – Prefix Equality
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
const int INF = 1001001001;

int main() {
  int N;
  cin >> N;
  
  vector<int> a(N);
  vector<int> cntA(N);
  int cnt = 1;
  map<int, int> mp;
  rep(i, N) {
    int A;
    cin >> A;
    if (mp[A] != 0) {
      a[i] = mp[A];
      cntA[i] = cnt - 1;
    } else {
      mp[A] = cnt;
      a[i] = cnt;
      cntA[i] = cnt;
      cnt++;
    }
  }

  vector<int> b(N);
  vector<int> cntB(N);
  vector<int> maxB(N);
  set<int> stB;
  int mxB = 0;
  rep(i, N) {
    int B;
    cin >> B;
    if (mp[B] == 0) {
      b[i] = INF;
    } else {
      b[i] = mp[B];
    }
    stB.insert(b[i]);
    cntB[i] = stB.size();
    mxB = max(mxB, b[i]);
    maxB[i] = mxB;
  }
  
  int Q;
  cin >> Q;
  rep(i, Q) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    int cA = cntA[x];
    int cB = cntB[y];
    int mB = maxB[y];
    if (cA == cB && cB == mB) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
  return 0;
}