\(f _ i\coloneqq{}\)バス \(i\) で全員に弁当を配ることができるなら \(0\) 、できないなら \(1\) とした列 \(f=(f _ 1,f _ 2,\ldots,f _ N)\) を考えます。

休憩プラン \(i\ (1\le i\le M)\) が配布可能であることは、次の条件と同値です。

• \(f _ {L _ i}+f _ {L _ {i+1}}+\cdots+f _ {R _ i}=0\)

これは、\(f\) の累積和を求めておくことで、ひとつの計画あたり定数時間で判定することができます。

よって、全体で \(O(N+M)\) 時間でこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> S(N), P(N);
    for (int& s : S) {
        cin >> s;
    }
    for (int& p : P) {
        cin >> p;
    }

    vector<int> f(N);
    for (int i = 0; i < N; ++i) {
        f[i] = S[i] < P[i]; // 配ることができないなら 1
    }
    // 累積和を求める
    for (int i = 1; i < N; ++i) {
        f[i] += f[i - 1];
    }
    f.emplace(f.begin()); // 先頭に 0 を入れておく

    for (int i = 0; i < M; ++i) {
        int L, R;
        cin >> L >> R;
        --L;
        cout << (f[R] == f[L] ? "Yes" : "No") << endl; // 区間内の f がすべて 0 なら Yes
    }

    return 0;
}

N, M = map(int, input().split())

S = list(map(int, input().split()))
P = list(map(int, input().split()))
f = [1 if s < p else 0 for s, p in zip(S, P)] # 配ることができないなら 1

# 累積和を求める
for i in range(1, N):
    f[i] += f[i - 1]
f = [0] + f # 先頭に 0 を入れておく

for i in range(M):
    L, R = map(int, input().split())
    L -= 1
    print('Yes' if f[R] == f[L] else 'No') # 区間内の f がすべて 0 なら Yes