結果
問題 |
No.274 The Wall
|
ユーザー |
![]() |
提出日時 | 2015-08-28 23:14:11 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,428 bytes |
コンパイル時間 | 1,007 ms |
コンパイル使用メモリ | 92,960 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-17 18:46:32 |
合計ジャッジ時間 | 1,745 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> #include <set> using namespace std; bool comp(const pair<int,int>& x, const pair<int,int>& y){ if(x.second != y.second) return x.second < y.second; else return x.first < y.first; } int main(){ int n,m; cin >> n >> m; vector<int> L(n),R(n); for(int i=0; i<n; i++){ cin >> L[i] >> R[i]; } vector<pair<int,int>> v(n); for(int i=0; i<n; i++){ if(L[i] >= m/2){ swap(L[i], R[i]); L[i] = m-1 - L[i]; R[i] = m-1 - R[i]; } v[i] = {L[i], R[i]}; } sort(v.begin(), v.end(), comp); vector<pair<int,int>> next; next.push_back({-1,m}); for(int i=0; i<n; i++){ vector<pair<int,int>> next_; int r__ = m; int l__ = -1; int l = v[i].first; int r = v[i].second; int rl = m-1 - r; int rr = m-1 - l; for(int j=0; j<next.size(); j++){ if(next[j].first < l && r < next[j].second){ l__ = max(next[j].second, l__); //next_.push_back({r, next[j].second}); } if(next[j].first < rl && rr < next[j].second){ r__ = min(next[j].first, r__); //next_.push_back({next[j].first, rl}); } } if(l__ != -1){ next_.push_back({r, l__}); } if(r__ != m){ next_.push_back({r__, rl}); } swap(next, next_); } if(next.size() == 0){ cout << "NO" << endl; }else{ cout << "YES" << endl; } return 0; }