题目传送门:C-School_牛客小白月赛54 (nowcoder.com)
思路 / Thought
一般遇到时间的题,都会将单位统一化,比如统一成“分钟”,那么这么的a时b分,就相当于是第a * m + b分钟。问题就转化成了给定一个1e13规模的区域,有1e3个区间,然后给定一个点问是否在这些区间覆盖的地方。
先读入区间,根据左端点排序,然后将区间合并成互不相交的若干个区间。
最后判断x点是否被覆盖了,只需要找到最后一个小于等于x的左端点(第一个大于x的左端点的前一个),判断右端点是否大于等于x即可。
代码 / Code
#include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; void solve() { int n, h, m, q;cin >> n >> h >> m >> q; vector<pair<int, int> > v, t;//t是合并后的区间数组 for(int i = 1;i <= n; ++ i) { int a, b, c, d;cin >> a >> b >> c >> d; a = a * m + b, c = c * m + d; v.push_back({a, c}); } sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b){return a.fi < b.fi;}); t.push_back(v[0]); for(auto &i : v) { if(i.fi <= t.back().se)t.back().se = max(t.back().se, i.se); else t.push_back(i); } while(q --) { int x, y;cin >> x >> y; x = x * m + y; int pos = upper_bound(t.begin(), t.end(), x, [](const int &a, const pair<int, int> &b){return a < b.fi;}) - t.begin() - 1; if(pos < t.size() && t[pos].fi <= x && x <= t[pos].se)cout << "No" << '\n'; else cout << "Yes" << '\n'; } } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; while(_ --)solve(); return 0; }
Comments NOTHING