提出 #75672665

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define pb push_back

template<class T> inline bool chmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int MOD = 1e9 + 7;

vector<int> bit;

void add(int idx, int val, int last) {
    for (; idx <= last; idx += idx & -idx) {
        bit[idx] += val;
    }
}

int query(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & -idx)
        sum += bit[idx];
    return sum;
}

void solve() {
    int n, m;
cin>>n>>m;
    vector<array<int, 3>> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = i;
    }
    int q;cin>>q;
    vector<array<int, 3>> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i][0] >> queries[i][1];
        queries[i][2] = i;
    }

    bit.assign(n + 2, 0);

    vector<array<int, 3>> byL = a;
    vector<array<int, 3>> byR = a;
    vector<array<int, 3>> byLd = a;

    sort(byL.begin(), byL.end(), [](const array<int, 3>& x, const array<int, 3>& y) {
        if (x[0] != y[0]) return x[0] < y[0];
        return x[1] > y[1];
    });

    sort(byR.begin(), byR.end(), [](const array<int, 3>& x, const array<int, 3>& y) {
        if (x[1] != y[1]) return x[1] < y[1];
        return x[0] < y[0];
    });

    sort(byLd.begin(), byLd.end(), [](const array<int, 3>& x, const array<int, 3>& y) {
        return x[0] > y[0];
    });

    sort(queries.begin(), queries.end(), [](const array<int, 3>& x, const array<int, 3>& y) {
        return x[0] > y[0];
    });

    vector<string> ans(q);
    int ptr = 0;

    for (int i = 0; i < q; i++) {
        int S = queries[i][0];
        int T = queries[i][1];
        int curr = queries[i][2];

        while (ptr < m && byLd[ptr][0] >= S) {
            add(byLd[ptr][1], 1, n);
            ptr++;
        }




        bool flag = false;

        vector<array<int, 3>> c1;
        array<int, 3> temp1 = {S, -1, -1};
        auto it1 = lower_bound(byL.begin(), byL.end(), temp1, [](const array<int, 3>& x, const array<int, 3>& y) {
            return x[0] < y[0];
        });
        for (int j = 0; j < 2 && it1 != byL.end() && (*it1)[0] == S; ++j, ++it1) {
            c1.pb(*it1);
        }
        vector<array<int, 3>> c2;
        array<int, 3> temp2 = {-1, T, -1};
        auto it2 = lower_bound(byR.begin(), byR.end(), temp2, [](const array<int, 3>& x, const array<int, 3>& y) {
            return x[1] < y[1];});
        for (int j = 0; j < 2 && it2 != byR.end() && (*it2)[1] == T; ++j, ++it2) {
            c2.pb(*it2);}
        for (auto u : c1) {
            for (auto v : c2) {
                if (u[2] != v[2] && v[0] <= u[1] + 1) {
                    flag = true;
                }
            }}
        if (!flag) {
            bool exact = false;
            for (auto u : c1) {
                if (u[1] == T) exact = true;
            }
            if (exact) {


                int cnt = query(T);
                if (cnt >= 2) {
                    flag= true;
                }
            }
        }
        ans[curr]= flag?"Yes" : "No";
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

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

    int tt = 1;
    while (tt--) {
        solve();
    }

    return 0;
}

提出情報

ジャッジ結果