結果
問題 | No.274 The Wall |
ユーザー | logx |
提出日時 | 2021-07-24 11:53:50 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 408 ms / 2,000 ms |
コード長 | 3,574 bytes |
コンパイル時間 | 2,163 ms |
コンパイル使用メモリ | 181,204 KB |
実行使用メモリ | 132,412 KB |
最終ジャッジ日時 | 2023-09-26 22:38:14 |
合計ジャッジ時間 | 4,857 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 146 ms
68,584 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 408 ms
132,412 KB |
testcase_12 | AC | 21 ms
4,380 KB |
testcase_13 | AC | 3 ms
4,376 KB |
testcase_14 | AC | 8 ms
4,376 KB |
testcase_15 | AC | 16 ms
4,376 KB |
testcase_16 | AC | 122 ms
39,480 KB |
testcase_17 | AC | 115 ms
37,692 KB |
testcase_18 | AC | 127 ms
40,740 KB |
testcase_19 | AC | 28 ms
4,380 KB |
testcase_20 | AC | 33 ms
4,376 KB |
testcase_21 | AC | 34 ms
4,380 KB |
testcase_22 | AC | 35 ms
4,376 KB |
testcase_23 | AC | 35 ms
4,376 KB |
testcase_24 | AC | 35 ms
4,376 KB |
testcase_25 | AC | 36 ms
4,376 KB |
ソースコード
#ifdef LOGX #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> using namespace std; //#include <atcoder/all> //using namespace atcoder; /*---------macro---------*/ #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = s; i < (int)(n); i++) #define unless(x) if(!(x)) #define until(x) while(!(x)) #define ALL(a) a.begin(),a.end() #define RALL(a) a.rbegin(),a.rend() #define mybit(i,j) (((i)>>(j))&1) /*---------type/const---------*/ const int big=1000000007; //const int big=998244353; const double EPS=1e-8; //適宜変える typedef long long ll; typedef unsigned long long ull; typedef std::string::const_iterator state; //構文解析 const int dx[4]={1,0,-1,0}; const int dy[4]={0,1,0,-1}; const char newl='\n'; struct{ constexpr operator int(){return -int(1e9)-10;} constexpr operator ll(){return -ll(1e18)-10;} }neginf; struct{ constexpr operator int(){return int(1e9)+10;} constexpr operator ll(){return ll(1e18)+10;} constexpr auto operator -(){return neginf;} }inf; /*---------debug---------*/ #ifdef LOGX #include <template/debug.hpp> #else #define dbg(...) ; #define dbgnewl ; #define prt(x) ; #define _prt(x) ; #endif /*---------function---------*/ template<typename T> T max(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=max(ans,elem);}return ans;} template<typename T> T min(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=min(ans,elem);}return ans;} template<typename T,typename U> bool chmin(T &a,const U b){if(a>b){a=b;return true;}return false;} template<typename T,typename U> bool chmax(T &a,const U b){if(a<b){a=b;return true;}return false;} bool valid(int i,int j,int h,int w){return (i>=0 && j>=0 && i<h && j<w);} template<class T,class U>T expm(T x,U y,const ll mod=big){T res=1;while(y){if(y&1)(res*=x)%=mod;(x*=x)%=mod;y>>=1;}return res;} template<class T,class U>T exp(T x,U y){T res=1;while(y){if(y&1)res*=x;x*=x;y>>=1;}return res;} int main(){ //std::ios::sync_with_stdio(false); //std::cin.tie(nullptr); std::cout.precision(10); /*------------------------------------*/ int n,m; cin >> n >> m; vector<int> l[2],r[2]; l[0]=l[1]=r[0]=r[1]=vector<int>(n); rep(i,n){ cin >> l[0][i] >> r[0][i],r[0][i]++; l[1][i]=m-r[0][i]; r[1][i]=m-l[0][i]; } vector<vector<int>> g(2*n),ginv(2*n); //[i:x] => [j:y] auto add=[&](int i,bool x,int j,bool y){ i+=(x ? 0:n); j+=(y ? 0:n); g[i].emplace_back(j); ginv[j].emplace_back(i); }; dbg(l[0]); dbg(r[0]); //「どの2つのペアを見ても、各列にピンクが高々1つ」 rep(i,n)rep2(j,i+1,n)rep(k,2)rep(m,2){ //交叉があるなら少なくとも一方が違う unless(r[k][i]<=l[m][j] || r[m][j]<=l[k][i]){ dbg(i,j,k,m); add(i,k,j,!m); add(j,m,i,!k); } } vector<int> res(2*n); vector<bool> al(2*n,false); vector<int> vertex; vertex.reserve(2*n); auto dfs=[&](int v,auto &dfs)->void{ al[v]=true; for(int ne:g[v])if(!al[ne])dfs(ne,dfs); vertex.emplace_back(v); }; rep(i,2*n)if(!al[i])dfs(i,dfs); reverse(ALL(vertex)); al.assign(2*n,false); auto dfs2=[&](int v,int now,auto &dfs2)->void{ al[v]=true; res[v]=now; for(int ne:ginv[v])if(!al[ne])dfs2(ne,now,dfs2); }; int now=0; for(int i:vertex)if(!al[i])dfs2(i,now++,dfs2); bool ok=true; rep(i,n){ ok&=res[i]!=res[i+n]; } cout << (ok ? "YES":"NO") << newl; }