結果
問題 | No.274 The Wall |
ユーザー |
|
提出日時 | 2024-03-07 22:23:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,151 ms / 2,000 ms |
コード長 | 3,407 bytes |
コンパイル時間 | 3,062 ms |
コンパイル使用メモリ | 225,948 KB |
最終ジャッジ日時 | 2025-02-20 01:46:11 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef unsigned long long int ull;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());ll myRand(ll B) {return (ull)rng() % B;}inline double time() {return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;}vector<int> scc(const vector<vector<int>> &g) {int n = (int)g.size();int cnt = 0;vector<vector<int>> rg(n);vector<int> order;vector<int> res(n, -1);vector<bool> used(n);for (int i = 0; i < n; ++i) {for (int j : g[i]) rg[j].push_back(i);}auto dfs1 = [&](auto self, int s) -> void {used[s] = true;for (int t : g[s]) {if (!used[t]) self(self, t);}order.push_back(s);};auto dfs2 = [&](auto self, int s) -> void {for (int t : rg[s]) {if (res[t] == -1) {res[t] = res[s];self(self, t);}}};order.reserve(n);for (int i = 0; i < n; ++i) {if (!used[i]) {dfs1(dfs1, i);}}reverse(order.begin(), order.end());for (int i : order) {if (res[i] == -1) {res[i] = cnt++;dfs2(dfs2, i);}}return res;}struct twosat {int n;vector<vector<int>> g;twosat(int n) : n(n), g(2*n) {}// (i = f1) || (j = f2)void add_clause(int i, bool f1, int j, bool f2) {g[(i << 1) ^ !f1].emplace_back((j << 1) ^ f2);g[(j << 1) ^ !f2].emplace_back((i << 1) ^ f1);}// (i = f1) -> (j = f2) <=> (i = !f1) || (j = f2)void add_if(int i, bool f1, int j, bool f2) {add_clause(i, !f1, j, f2);}// ivoid set_true(int i) {add_clause(i, true, i, true);}// !ivoid set_false(int i) {add_clause(i, false, i, false);}vector<bool> solve() {vector<int> c = scc(g);vector<bool> res(n);for (int i = 0; i < n; ++i) {if (c[i << 1] == c[i << 1 | 1]) return vector<bool>();res[i] = (c[i << 1] < c[i << 1 | 1]);}return res;}};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n; cin >> n;int m; cin >> m;vector<int> l(n), r(n);for (int i = 0; i < n; ++i) {cin >> l[i] >> r[i];l[i] += 1;r[i] += 1;}twosat ts(n);for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (i == j) continue;auto check = [&](int l1, int r1, int l2, int r2) -> bool {return max(l1, l2) > min(r1, r2);};if (!check(l[i], r[i], l[j], r[j])) {ts.add_if(i, false, j, true);}if (!check(l[i], r[i], m+1-r[j], m+1-l[j])) {ts.add_if(i, false, j, false);}if (!check(m+1-r[i], m+1-l[i], l[j], r[j])) {ts.add_if(i, true, j, true);}if (!check(m+1-r[i], m+1-l[i], m+1-r[j], m+1-l[j])) {ts.add_if(i, true, j, false);}}}if (ts.solve().size()) {cout << "YES" << endl;}else {cout << "NO" << endl;}}