C、School

前置知识：区间合并+二分查找

区间合并：对于多个区间来说，如果其中有区间的范围有重合，那便可以把他们合并成一个区间，这样做对于某些对区间的处理就能方便简洁很多。

问题解析

为了方便处理，我们可以直接把所有时间改成分钟的形式，比如1小时10分，对于我们正常的时间来说，这就是70分，那么1小时10分到2小时20分，就是70分中到140分钟。

我们直接把所有的不能打电话的时间段转化成分钟形式的区间，对于样例来说：

输入
3 24 60 2
7 0 11 15
14 20 17 35
18 50 21 10
7 1
21 11

输出
No
Yes

不能打电话的时间段就为：

• 420 ~ 675
• 860 ~ 1055
• 1130 ~ 1270

然后我们再把要打电话的时间也转化成分钟，再二分查找下我们要打电话的时间有没有出现在这些时间段即可，如果出现了，就是No，反之是Yes。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6+50, MOD = 1e9+7;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}

void solve()
{
    int n, h, m, q, a, b, c, d;
    vector<PII>v, st;
    cin >> n >> h >> m >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b >> c >> d;
        int l = a * m + b, r = c * m + d;
        v.push_back({ l,r });
    }
    sort(v.begin(), v.end());
    st.push_back(v[0]);
    int len = v.size();
    for (int i = 1; i < len; i++)
    {
        if (v[i].first <= st.back().second)
        {
            st.back().second = max(v[i].second, st.back().second);
        }
        else
        {
            st.push_back(v[i]);
        }
    }
    sort(st.begin(),st.end());
    while (q--)
    {
        cin >> a >> b;
        int x = a * m + b;
        int l = 0, r = st.size() - 1;
        bool flag = true;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (st[mid].first <= x && st[mid].second >= x)
            {
                cout << "No" << endl;
                flag = false;
                break;
            }
            else if (st[mid].first > x)r = mid - 1;
            else if (st[mid].second < x)l = mid + 1;
        }
        if (flag)cout << "Yes" << endl;
    }

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}