結果
| 問題 | No.274 The Wall |
| ユーザー |
 cutmdo
|
| 提出日時 | 2021-07-16 00:45:17 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 57 ms / 2,000 ms |
| コード長 | 5,885 bytes |
| コンパイル時間 | 11,793 ms |
| コンパイル使用メモリ | 304,676 KB |
| 最終ジャッジ日時 | 2025-01-23 01:12:11 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 22 |
ソースコード
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,avx512f")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <iostream>#include <iomanip>#include <string>#include <cmath>#include <algorithm>#include <vector>#include <set>#include <map>#include <unordered_map>#include <unordered_set>#include <list>#include <stack>#include <queue>#include <bitset>#include <numeric>#include <cassert>#include <memory>#include <random>#include <functional>#include <complex>#include <immintrin.h>#ifdef DEBUG#include "./CompetitiveProgrammingCpp/debug_VC.hpp"#include "./CompetitiveProgrammingCpp/Timer.hpp"#include "./CompetitiveProgrammingCpp/sample.hpp"#else#define dump(...)#endif/* macro */#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)#define REP(i, n) FOR(i, 0, n)#define RREP(i, n) RFOR(i, 0, n)#define REPC(x,c) for(const auto& x:(c))#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)#define REPI(it,c) REPI2(it, (c).begin(), (c).end())#define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend())#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())#define ALL(x) (x).begin(),(x).end()#define cauto const auto&/* macro func */template<class T>inline auto sort(T& t) { std::sort(ALL(t)); }template<class T>inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); }template<class T>inline auto unique(T& t) { (t).erase(unique((t).begin(), (t).end()), (t).end()); }template<class T, class S>inline auto chmax(T& t, const S& s) { if (s > t) { t = s; return true; } return false; }template<class T, class S>inline auto chmin(T& t, const S& s) { if (s < t) { t = s; return true; } return false; }inline auto BR() { std::cout << "\n"; }/* type define */using ll = long long;using PAIR = std::pair<ll, ll>;using VS = std::vector<std::string>;using VL = std::vector<long long>;using VVL = std::vector<VL>;using VVVL = std::vector<VVL>;using VD = std::vector<double>;template<class T>using V = std::vector<T>;/* using std */using std::cout;constexpr char endl = '\n';using std::cin;using std::pair;using std::string;using std::stack;using std::queue;using std::vector;using std::list;using std::map;using std::unordered_map;using std::multimap;using std::unordered_multimap;using std::set;using std::unordered_set;using std::unordered_multiset;using std::multiset;using std::bitset;using std::priority_queue;/* Initial processing */struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;/* Remove the source of the bug */auto pow(signed, signed) { assert(false); return -1; }/* define hash */namespace std {template <> class hash<std::pair<ll, ll>> { public: size_t operator()(const std::pair<ll, ll>& x) const { return hash<ll>()(1000000000 * x.first + x.second); } };}/* input */template<class T> std::istream& operator >> (std::istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }/* constant value *///constexpr ll MOD = 1000000007;constexpr ll MOD = 998244353;//=============================================================================================class SCC {const int m_n;const std::unordered_multimap<int, int> m_graph;const std::unordered_multimap<int, int> m_revGraph;const std::vector<int> m_group;auto reverse()const {std::unordered_multimap<int, int> graph;for (const auto& [f, t] : m_graph) { graph.emplace(t, f); }return graph;}template<class Lambda>auto dfs(int n,const std::unordered_multimap<int, int>& graph,int root,std::vector<int>& isUsed,const Lambda& lambda) const {isUsed[root] = true;std::stack<int> q; q.emplace(root);while (!q.empty()) {auto from = q.top();q.pop();auto range = graph.equal_range(from);for (auto itr = range.first; itr != range.second; ++itr) {auto to = itr->second;if (!isUsed[to]) {q.emplace(to);isUsed[to] = true;lambda(from, to);}}}}auto constructGroup()const {std::list<int> order;{std::vector<int> used(m_n);for (int from = 0; from < m_n; ++from) if (!used[from]) {std::list<int> localOrder;localOrder.emplace_front(from);dfs(m_n, m_graph, from, used, [&](int f, int t) {used[t] = true;localOrder.emplace_front(t);});for (const auto& x : localOrder) {order.emplace_front(x);}}}std::vector<int> group(m_n);{std::vector<int> used(m_n);int g = 0;for (const auto& from : order) if (!used[from]) {group[from] = g;dfs(m_n, m_revGraph, from, used, [&](int f, int t) {used[t] = true;group[t] = g;});++g;}}return group;}public:SCC(int n, const std::unordered_multimap<int, int>& graph) :m_n(n),m_graph(graph),m_revGraph(reverse()),m_group(constructGroup()) {}auto isSameGroup(int a, int b)const {return m_group[a] == m_group[b];}};signed main() {ll n, m;cin >> n >> m;V<PAIR> v;ll sum = 0;v.reserve(2 * n);REP(_, n) {ll a, b;cin >> a >> b;v.emplace_back(a, b);sum += b - a + 1;}if (sum > m) {cout << "NO" << endl;return 0;}REP(i, n) {v.emplace_back(m - v[i].second - 1, m - v[i].first - 1);}unordered_multimap<int, int> graph;REP(i, 2 * n)FOR(j, i + 1, 2 * n) {if (v[i].second < v[j].first || v[j].second < v[i].first) { continue; }ll ni = (i < n) ? i + n : i - n;ll nj = (j < n) ? j + n : j - n;graph.emplace(ni, j);graph.emplace(nj, i);}auto scc = SCC(2 * n, graph);REP(i, n) if (scc.isSameGroup(i, i + n)) {cout << "NO" << endl;return 0;}cout << "YES" << endl;}