結果
問題 |
No.2687 所により大雨
|
ユーザー |
👑 |
提出日時 | 2024-03-03 14:22:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 384 ms / 2,000 ms |
コード長 | 2,371 bytes |
コンパイル時間 | 2,781 ms |
コンパイル使用メモリ | 258,240 KB |
実行使用メモリ | 9,124 KB |
最終ジャッジ日時 | 2024-09-30 05:59:26 |
合計ジャッジ時間 | 8,453 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; assert(1 <= n and n <= 100000); assert(1 <= m and m <= 1000); vector<long long> L1(n), R1(n); for (int i = 0; i < n; i++) { cin >> L1[i] >> R1[i]; assert(-1000000000 <= L1[i] and L1[i] <= R1[i] and R1[i] <= 1000000000); } vector<long long> L2(m), R2(m); for (int i = 0; i < m; i++) { cin >> L2[i] >> R2[i]; assert(-1000000000 <= L2[i] and L2[i] <= R2[i] and R2[i] <= 1000000000); } int k; cin >> k; assert(1 <= k and k <= 1000); vector<int> P(k); for (int i = 0; i < k; i++) { cin >> P[i]; assert(-1000000000 <= P[i] and P[i] <= 1000000000); if (i != 0) assert(P[i - 1] < P[i]); } auto merge = [](vector<long long> L, vector<long long> R) { int n = L.size(); vector<int> inds(n); iota(inds.begin(), inds.end(), 0); sort(inds.begin(), inds.end(), [&](int i, int j) { return L[i] < L[j]; }); vector<long long> res; for (auto i : inds) { int l = L[i]; int r = R[i]; if (res.empty() or res.back() < l) { res.push_back(l); res.push_back(r); } else { res.back() = r; } } return res; }; auto LR1 = merge(L1, R1); auto LR2 = merge(L2, R2); if (int(LR1.size()) != 2 * n or int(LR2.size()) != 2 * m) { for (int i = 0; i < k; i++) { if (i != 0) cout << " "; cout << 1; } cout << endl; return 0; } vector<int> ans(k); for (int i = 0; i < k; i++) { ans[i] = 0; long long p = P[i] * 2; int mp = 2 * m; for (int j = 0; j < n; j++) { int l = LR1[2 * j]; int r = LR1[2 * j + 1]; while (mp >= 1 and LR2[mp - 1] + l > p) { mp--; } int p1 = mp; while (mp >= 1 and LR2[mp - 1] + r >= p) { mp--; } int p2 = mp; if (p1 != p2 or p1 % 2 == 1) { ans[i] = 1; break; } } } for (int i = 0; i < k; i++) { if (i != 0) cout << " "; cout << ans[i]; } cout << endl; }