結果
| 問題 | No.274 The Wall |
| ユーザー |
 はむこ
|
| 提出日時 | 2017-07-06 16:22:06 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 11,451 bytes |
| コンパイル時間 | 2,123 ms |
| コンパイル使用メモリ | 203,236 KB |
| 実行使用メモリ | 765,184 KB |
| 最終ジャッジ日時 | 2024-10-06 03:38:29 |
| 合計ジャッジ時間 | 7,043 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,824 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 1 ms
6,820 KB |
| testcase_03 | AC | 428 ms
329,344 KB |
| testcase_04 | AC | 2 ms
5,248 KB |
| testcase_05 | AC | 2 ms
5,248 KB |
| testcase_06 | AC | 2 ms
5,248 KB |
| testcase_07 | AC | 1 ms
5,248 KB |
| testcase_08 | AC | 1 ms
5,248 KB |
| testcase_09 | AC | 2 ms
5,248 KB |
| testcase_10 | AC | 1 ms
5,248 KB |
| testcase_11 | MLE | - |
| testcase_12 | AC | 32 ms
6,816 KB |
| testcase_13 | AC | 2 ms
6,816 KB |
| testcase_14 | AC | 8 ms
6,820 KB |
| testcase_15 | AC | 17 ms
6,820 KB |
| testcase_16 | AC | 464 ms
296,192 KB |
| testcase_17 | AC | 437 ms
280,928 KB |
| testcase_18 | AC | 457 ms
302,956 KB |
| testcase_19 | AC | 30 ms
6,820 KB |
| testcase_20 | AC | 35 ms
6,820 KB |
| testcase_21 | AC | 35 ms
6,816 KB |
| testcase_22 | AC | 38 ms
6,816 KB |
| testcase_23 | AC | 38 ms
6,816 KB |
| testcase_24 | AC | 38 ms
6,820 KB |
| testcase_25 | AC | 39 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
#define ZERO(a) memset(a,0,sizeof(a))
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
#define exists find_if
#define forall all_of
using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
using ld = long double; using vld = vector<ld>;
using vi = vector<int>; using vvi = vector<vi>; vll conv(vi& v) { vll r(v.size()); rep(i, v.size()) r[i] = v[i]; return r; }
using Pos = complex<double>;
template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) { o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args>
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; o << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]"; return o; }
template <typename T> ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]"; return o; }
template <typename T, typename U> ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]"; return o; }
template <typename T, typename U, typename V> ostream &operator<<(ostream &o, const unordered_map<T, U, V> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]"; return o; }
vector<int> range(const int x, const int y) { vector<int> v(y - x + 1); iota(v.begin(), v.end(), x); return v; }
template <typename T> istream& operator>>(istream& i, vector<T>& o) { rep(j, o.size()) i >> o[j]; return i;}
string bits_to_string(ll input, ll n=64) { string s; rep(i, n) s += '0' + !!(input & (1ll << i)); reverse(all(s)); return s; }
template <typename T> unordered_map<T, ll> counter(vector<T> vec){unordered_map<T, ll> ret; for (auto&& x : vec) ret[x]++; return ret;};
string substr(string s, P x) {return s.substr(x.fi, x.se - x.fi); }
struct ci : public iterator<forward_iterator_tag, ll> { ll n; ci(const ll n) : n(n) { } bool operator==(const ci& x) { return n == x.n; } bool operator!=(const ci& x) { return !(*this == x); } ci &operator++() { n++; return *this; } ll operator*() const { return n; } };
size_t random_seed; namespace std { using argument_type = P; template<> struct hash<argument_type> { size_t operator()(argument_type const& x) const { size_t seed = random_seed; seed ^= hash<ll>{}(x.fi); seed ^= (hash<ll>{}(x.se) << 1); return seed; } }; }; // hash for various class
namespace myhash{ const int Bsizes[]={3,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81}; const int xor_nums[]={0x100007d1,0x5ff049c9,0x14560859,0x07087fef,0x3e277d49,0x4dba1f17,0x709c5988,0x05904258,0x1aa71872,0x238819b3,0x7b002bb7,0x1cf91302,0x0012290a,0x1083576b,0x76473e49,0x3d86295b,0x20536814,0x08634f4d,0x115405e8,0x0e6359f2}; const int hash_key=xor_nums[rand()%20]; const int mod_key=xor_nums[rand()%20]; template <typename T> struct myhash{ std::size_t operator()(const T& val) const { return (hash<T>{}(val)%mod_key)^hash_key; } }; };
template <typename T> class uset:public std::unordered_set<T,myhash::myhash<T>> { using SET=std::unordered_set<T,myhash::myhash<T>>; public: uset():SET(){SET::rehash(myhash::Bsizes[rand()%20]);} };
template <typename T,typename U> class umap:public std::unordered_map<T,U,myhash::myhash<T>> { public: using MAP=std::unordered_map<T,U,myhash::myhash<T>>; umap():MAP(){MAP::rehash(myhash::Bsizes[rand()%20]);} };
struct timeval start; double sec() { struct timeval tv; gettimeofday(&tv, NULL); return (tv.tv_sec - start.tv_sec) + (tv.tv_usec - start.tv_usec) * 1e-6; }
struct init_{init_(){ gettimeofday(&start, NULL); ios::sync_with_stdio(false); cin.tie(0); srand((unsigned int)time(NULL)); random_seed = RAND_MAX / 2 + rand() / 2; }} init__;
static const double EPS = 1e-14;
static const long long mo = 1e9+7;
#define ldout fixed << setprecision(40)
/***********************/
// 共通部分
/***********************/
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long Weight;
const Weight INF = 1e18;
struct Edge {
ll src, dst;
Weight weight; // 最小費用流ではcostの役割
ll cap;
ll rev; // 残余グラフの対応用
bool rev_flag = false; // revなら1
Edge(int src = 0, int dst = 0, int weight = 0, Weight cap = 1):
src(src), dst(dst), weight(weight), cap(cap){ }
};
bool operator < (const Edge &e, const Edge &f) {
return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
// 最大流と最小費用流の有向
// 無向は自分でひっくり返して追加して下さい
void addDirected(Graph& g, ll src, ll dst, Weight weight = 0, ll cap = 0) {
assert(src < g.size() && src >= 0 && dst < g.size() && dst >= 0);
g[src].push_back(Edge(src, dst, weight, cap));
}
vector<string> names;
unordered_map<string, int> name_server;
void clearNameServer(void) {
names.clear();
name_server.clear();
}
int constructNameServer(vector<string>& names_) {
names = names_;
for (int i = 0; i < names.size(); i++) {
name_server[names[i]] = i;
}
return name_server.size();
}
void addDirected(Graph& g, string src, string dst, Weight weight = 0, ll cap = 0) {
if (!name_server.count(src)) { cerr << "No such node : " << src << endl; exit(1); }
if (!name_server.count(dst)) { cerr << "No such node : " << dst << endl; exit(1); }
addDirected(g, name_server[src], name_server[dst], weight, cap);
}
void addUndirected(Graph& g, ll src, ll dst, Weight weight = 0, ll cap = 0) {
addDirected(g, src, dst, weight, cap);
addDirected(g, dst, src, weight, cap);
}
void transformFromMatrixToGraph(Graph& g, Matrix& m) {
ll n = m.size();
g.resize(n);
rep(i, n) rep(j, n) if (m[i][j] != INF) {
addDirected(g, i, j, m[i][j]);
}
}
void printGraph(Graph& g) {
rep(i, g.size()) {
cout << i << " : ";
rep(j, g[i].size())
cout << g[i][j].dst << ", ";
cout << endl;
}
}
void printGraphCap(Graph& g) {
rep(i, g.size()) {
if (!g[i].size())
continue;
rep(j, g[i].size())
cout << "(" << i << ", " << g[i][j].dst << " : " << g[i][j].cap << ", " << (g[i][j].rev_flag ? "rev" : "for") << "), ";
cout << endl;
}
}
// 強連結分解
// O(V+E)
// const Graph& g 有向グラフ
// vector< vector<ll> >& scc グラフの強連結成分
void visitStronglyConnectedComponents(const Graph &g, ll v, vector< vector<ll> >& scc,
stack<ll> &S, vector<bool> &inS,
vector<ll> &low, vector<ll> &num, ll& time) {
low[v] = num[v] = ++time;
S.push(v); inS[v] = true;
FOR(e, g[v]) {
ll w = e->dst;
if (num[w] == 0) {
visitStronglyConnectedComponents(g, w, scc, S, inS, low, num, time);
low[v] = min(low[v], low[w]);
} else if (inS[w])
low[v] = min(low[v], num[w]);
}
if (low[v] == num[v]) {
scc.push_back(vector<ll>());
while (1) {
ll w = S.top(); S.pop(); inS[w] = false;
scc.back().push_back(w);
if (v == w) break;
}
}
}
void stronglyConnectedComponents(const Graph& g, vector< vector<ll> >& scc) {
const ll n = g.size();
vector<ll> num(n), low(n);
stack<ll> S;
vector<bool> inS(n);
ll time = 0;
rep(u, n) if (num[u] == 0)
visitStronglyConnectedComponents(g, u, scc, S, inS, low, num, time);
}
#define NOT(a) ((a)+n)
#define flip(i) (tie(l[i], r[i]) = mt(m-r[i]-1, m-l[i]-1))
ll cross(ll l1, ll r1, ll l2, ll r2) {
// cout << l1 << " "<< r1 << " " << l2 << " " << r2 << endl;
if (l1 <= l2 && l2 <= r1) return 1;
if (l1 <= r2 && r2 <= r1) return 1;
if (l2 <= l1 && l1 <= r2) return 1;
if (l2 <= r1 && r1 <= r2) return 1;
// cout << "OK" << endl;
return 0;
}
int main(void) {
assert(cross(0,2,1,2) ==1);
ll n, m; cin >> n >> m;
vll l(n), r(n);
rep(i, n) {
cin >> l[i] >> r[i];
}
Graph g(2*n);
rep(i, n) repi(j, i+1, n) {
// cout << "####" << endl;
// iがそのままとjがそのままが両立しない
// cout << P(l[i], r[i]) << " " << P(l[j], r[j]) << endl;;
if (cross(l[i], r[i], l[j], r[j])) {
// cout << "i, j" << endl;
addDirected(g, i, NOT(j));
addDirected(g, j, NOT(i));
}
// iが逆とjがそのままが両立しない
flip(i);
// cout << P(l[i], r[i]) << " " << P(l[j], r[j]) << endl;;
if (cross(l[i], r[i], l[j], r[j])) {
// cout << "not i, j" << endl;
addDirected(g, NOT(i), NOT(j));
addDirected(g, j, i);
}
// iが逆とjが逆が両立しない
flip(j);
// cout << P(l[i], r[i]) << " " << P(l[j], r[j]) << endl;;
if (cross(l[i], r[i], l[j], r[j])) {
// cout << "not i, not j" << endl;
addDirected(g, NOT(i), j);
addDirected(g, NOT(j), i);
}
// iがそのままとjが逆が両立しない
flip(i);
// cout << P(l[i], r[i]) << " " << P(l[j], r[j]) << endl;;
if (cross(l[i], r[i], l[j], r[j])) {
// cout << "i, not j" << endl;
addDirected(g, i, j);
addDirected(g, NOT(j), NOT(i));
}
flip(j);
// cout << P(l[i], r[i]) << " " << P(l[j], r[j]) << endl;;
}
// printGraph(g);
vector<vector<ll>> scc;
stronglyConnectedComponents(g, scc);
rep(i, scc.size()) {
// rep(j, scc[i].size()) cout << scc[i][j] << " ";
// cout << endl;
}
rep(i, scc.size()) {
unordered_set<ll> s;
for (auto x : scc[i]) {
s.insert(x);
}
for (auto x : scc[i]) {
if (s.count(n + x)) {
cout << "NO" << endl;
return 0;
}
}
}
cout << "YES" << endl;
return 0;
}