Competitive-programming/M-islands.cpp at main · MohamedAboElsaud/Competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

/*
|||   ╔═══════════╗            ╔════╗            ╔═══════════╗    ╔═══════════╗    ╔══════════╗       |||
|||   ║███████████║            ║████║            ║███████████║    ║███████████║    ║██████████║       |||
|||   ║██╔════════╝           ║██║║██║           ║██╔════════╝    ║██╔════════╝    ║██══════╗██║      |||
|||   ║██║                   ║██║╔╗║██║          ║██║             ║██║             ║██       ║██║     |||
|||   ║██╚════════╗         ║██║╔╚╝╗║██║         ║██╚════════╗    ║██╚════════╗    ║██        ║██║    |||
|||   ║███████████║        ║██║ ╚══╝ ║██║        ║███████████║    ║███████████║    ║██         ║██║   |||
|||   ╚════════╗██║       ║██║██║██║██║██║       ║██╔════════╝    ║██╔════════╝    ║██        ║██║    |||
|||            ║██║      ║██║ ╔═╔══╗═╗ ║██║      ║██║             ║██║             ║██       ║██║     |||
|||   ╔════════╝██║     ║██║ ╔╚╔╚══╝╗╝╗ ║██║     ║██╚════════╗    ║██╚════════╗    ║██══════╝██║      |||
|||   ║███████████║    ║██║ ╔╚╔╚════╝╗╝╗ ║██║    ║███████████║    ║███████████║    ║██████████║       |||
|||   ╚═══════════╝    ╚══╝ ╚═╚══════╝═╝ ╚══╝    ╚═══════════╝    ╚═══════════╝    ╚══════════╝       |||
|||                                                                                                   |||
|||                                                                                                   |||
|||                                  ╔════════╗  ╔════════════╗                                       |||
|||                         ║██║     ║████████║  ║████████████║     ║██║                              |||
|||    ║█║ ║█║            ║██║       ╚══║██║══╝  ╚════║██║════╝       ║██║            ║█║ ║█║         |||
|||   ║█ ║█║ █║         ║██║            ║██║          ║██║              ║██║         ║█ ║█║ █║        |||
|||    ║█   █║        ║██║              ║██║          ║██║                ║██║        ║█   █║         |||
|||     ║█║█║           ║██║            ║██║          ║██║              ║██║           ║█║█║          |||
|||      ║█║              ║██║       ╔══║██║══╗       ║██║            ║██║              ║█║           |||
|||                         ║██║     ║████████║      ╔║██║╗         ║██║                              |||
|||                                  ╚════════╝      ╚════╝                                           |||
*/

link :https://codeforces.com/group/u3Ii79X3NY/contest/270796/problem/K

#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ll long long int
#define ld long double


using namespace std;
void fast() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

ll n, m, a, b,l,r,res,md;
vector<pair<ll, ll>>v;
vector<pair<ll, ll>>vv(n);
void merge(pair<ll, ll>p) {
    res = -1,l=0,r=v.size()-1;
    while (l <= r) {
        md = l + (r - l) / 2;
        if (v[md].first <= p.first)res = md, l = md + 1;
        else r = md - 1;
    }
    if (res != -1 && p.first <= v[res].second) {
        v[res].first = min(v[res].first, p.first);
        v[res].second = max(v[res].second, p.second);
    }
    else v.push_back(p);
}

bool chk(ll a, ll b) {
    l = 0, r = v.size()-1, res = -1;
    while (l<=r)
    {
        md = l + (r - l) / 2;
        if (v[md].first <= a)res = md, l = md + 1;
        else r = md - 1;
    }

    if (res != -1)return v[res].second >= b;
    return 0;
}


int main()
{
    fast();
    cin >> n >> m;
    for (ll i = 0; i < n; i++) {
        cin >> a >> b;
        vv.push_back({ a,b });
    }
    sort(vv.begin(), vv.end());
    for (auto it : vv) {
        if (!v.empty())merge( it);
        else v.push_back(it);
    }
    cin >> n;
    while (n--) {
        cin >> a >> b;
        if (a > b)swap(a, b);
        if (chk(a, b))cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}