#133766 (C++11) No.274 The Wall

• 問題: No.274 The Wall
• ユーザー: srup٩(๑`н´๑)۶
• 提出日時: 2016-11-29 19:49:06
• 言語: C++11 (gcc 13.3.0)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 1,809 bytes
• コンパイル時間: 1,321 ms
• コンパイル使用メモリ: 171,920 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-06-22 02:11:43
• 合計ジャッジ時間: 2,097 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 4
other	AC * 22

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
set<pair<int, int> > S;
vector<pint> side;
int main(void){
    int n, m;
    cin >> n >> m;
    S.insert(mp(0, m - 1));
    rep(i, n){
        int tl, tr;
        cin >> tl >> tr;
        side.pb(mp(tl, tr));
    }
    rep(i, n){
        int l, r;
        l = side[i].fi, r = side[i].se;
        int rel = m - l - 1, rer = m - r - 1;
        if(rel > rer) swap(rel, rer);
        if(rel < l){
            side[i].fi = rel, side[i].se = rer;
        }
    }
    sort(all(side));
    rep(i, n){
        bool ok = false;
        int l = side[i].fi, r = side[i].se;
        // printf("l %d r %d\n", l, r);
        for(auto u : S){
            if(u.fi <= l && r <= u.se){
                if(u.fi != l){
                    S.insert(mp(u.fi, l - 1));
                }
                if(u.se != r){
                    S.insert(mp(r + 1, u.se));
                }
                S.erase(mp(u.fi, u.se));
                ok = true;
                break;
            }
        }
        if(!ok){//回転
            l = m - l - 1, r = m - r - 1;
            if(l > r)swap(l, r);
            // printf("dame %d %d\n", l, r);
            for(auto u : S){
                if(u.fi <= l && r <= u.se){
                    if(u.fi != l){
                        S.insert(mp(u.fi, l - 1));
                    }
                    if(u.se != r){
                        S.insert(mp(r + 1, u.se));
                    }
                    S.erase(mp(u.fi, u.se));
                    ok = true;
                    break;
                }
            }
        }
            
        /*
        for(auto v : S){
            printf("k %d %d\n", v.fi, v.se);
        }
        */
        
        if(!ok){
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX