結果

問題 No.274 The Wall
ユーザー hashiryo
提出日時 2024-09-03 20:49:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 4,908 bytes
コンパイル時間 2,129 ms
コンパイル使用メモリ 201,952 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-17 19:13:34
合計ジャッジ時間 2,992 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &u){if(!u)os<<"0";__int128_t tmp=u<0?(os<<"-",-u):u;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &u){if(!u)os<<"0";__uint128_t tmp=u;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
#define checkpoint() (void(0))
#define debug(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
template <bool undoable= false, class weight_t= void> class UnionFind {
 std::vector<int> par;
 std::vector<weight_t> val;
public:
 UnionFind(int n): par(n, -1), val(n) {}
 int leader(int u) {
  if (par[u] < 0) return u;
  int r= leader(par[u]);
  if constexpr (std::is_same_v<weight_t, bool>) val[u]= val[u] ^ val[par[u]];
  else val[u]+= val[par[u]];
  return par[u]= r;
 }
 //  p(v) - p(u) = w
 bool unite(int u, int v, weight_t w) {
  int u_= leader(u), v_= leader(v);
  if constexpr (std::is_same_v<weight_t, bool>) w^= val[u] ^ val[v];
  else w+= val[u] - val[v];
  if (u_ == v_) return w == weight_t();
  if (par[u_] > par[v_]) std::swap(u_, v_), w= -w;
  return par[u_]+= par[v_], par[v_]= u_, val[v_]= w, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
 weight_t potential(int u) { return leader(u), val[u]; }
 //  p(v) - p(u)
 weight_t diff(int u, int v) {
  if constexpr (std::is_same_v<weight_t, bool>) return potential(u) ^ potential(v);
  else return potential(v) - potential(u);
 }
};
template <> class UnionFind<false, void> {
 std::vector<int> par;
public:
 UnionFind(int n): par(n, -1) {}
 int leader(int u) { return par[u] < 0 ? u : par[u]= leader(par[u]); }
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par[u] > par[v]) std::swap(u, v);
  return par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
};
template <class T> class UnionFind<true, T> {
 std::vector<int> par;
 std::vector<T> val;
 std::vector<std::tuple<int, int, T>> his;
public:
 UnionFind(int n): par(n, -1), val(n) {}
 int leader(int u) const { return par[u] < 0 ? u : leader(par[u]); }
 //  p(v) - p(u) = w
 bool unite(int u, int v, T w) {
  int u_= leader(u), v_= leader(v);
  if constexpr (std::is_same_v<T, bool>) w^= val[u] ^ val[v];
  else w+= val[u] - val[v];
  if (u_ == v_) return w == T();
  if (par[u_] > par[v_]) std::swap(u_, v_), w= -w;
  return his.emplace_back(v_, par[v_], val[v_]), par[u_]+= par[v_], par[v_]= u_, val[v_]= w, true;
 }
 bool connected(int u, int v) const { return leader(u) == leader(v); }
 int size(int u) const { return -par[leader(u)]; }
 T potential(int u) {
  if constexpr (std::is_same_v<T, bool>) return par[u] < 0 ? val[u] : val[u] ^ potential(par[u]);
  else return par[u] < 0 ? val[u] : val[u] + potential(par[u]);
 }
 //  p(v) - p(u)
 T diff(int u, int v) {
  if constexpr (std::is_same_v<T, bool>) return potential(v) ^ potential(u);
  else return potential(v) - potential(u);
 }
 int time() const { return his.size(); }
 void undo() {
  if (his.empty()) return;
  auto [u, s, v]= his.back();
  his.pop_back(), par[par[u]]-= s, par[u]= s, val[u]= v;
 }
 void rollback(int t) {
  for (assert(t <= time()); time() > t;) undo();
 }
};
template <> class UnionFind<true, void> {
 std::vector<int> par;
 std::vector<std::pair<int, int>> his;
public:
 UnionFind(int n): par(n, -1) {}
 int leader(int u) const { return par[u] < 0 ? u : leader(par[u]); }
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par[u] > par[v]) std::swap(u, v);
  return his.emplace_back(v, par[v]), par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) const { return leader(u) == leader(v); }
 int size(int u) const { return -par[leader(u)]; }
 int time() const { return his.size(); }
 void undo() {
  if (his.empty()) return;
  auto [u, s]= his.back();
  his.pop_back(), par[par[u]]-= s, par[u]= s;
 }
 void rollback(int t) {
  for (assert(t <= time()); time() > t;) undo();
 }
};
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 int L[N], R[N];
 for (int i= 0; i < N; ++i) cin >> L[i] >> R[i];
 UnionFind<false, bool> uf(N);
 for (int i= N; i--;)
  for (int j= i; j--;) {
   if (!(R[i] < L[j] || R[j] < L[i]))
    if (!uf.unite(i, j, 1)) return cout << "NO" << '\n', 0;
   if (!(R[i] < M - 1 - R[j] || M - 1 - L[j] < L[i]))
    if (!uf.unite(i, j, 0)) return cout << "NO" << '\n', 0;
  }
 cout << "YES" << '\n';
 return 0;
}
0