Submission #61600651

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Interval {
    long long start, end;
};
int main() {
    long long N, M, A, B;
    cin >> N >> M >> A >> B;
    vector<Interval> bad_intervals(M);
    
    for (int i = 0; i < M; ++i) {
        cin >> bad_intervals[i].start >> bad_intervals[i].end;
    }
    // 良い区間を作成
    vector<Interval> good_intervals;
    long long last_end = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Interval {
    long long start, end;
};

int main() {
    long long N, M, A, B;
    cin >> N >> M >> A >> B;
    vector<Interval> bad_intervals(M);
    
    for (int i = 0; i < M; ++i) {
        cin >> bad_intervals[i].start >> bad_intervals[i].end;
    }

    // 良い区間を作成
    vector<Interval> good_intervals;
    long long last_end = 0;

    for (const auto& bad : bad_intervals) {
        if (last_end + 1 < bad.start) {
            good_intervals.push_back({last_end + 1, bad.start - 1});
        }
        last_end = bad.end;
    }

    if (last_end < N) {
        good_intervals.push_back({last_end + 1, N});
    }

    // 現在到達可能な範囲
    long long current_start = 1, current_end = 1;
    size_t idx = 0;

    while (current_start <= N) {
        long long next_start = -1, next_end = -1;

        // 良い区間を見つける
        while (idx < good_intervals.size() && good_intervals[idx].end < current_start + A) {
            ++idx;
        }

        while (idx < good_intervals.size() && good_intervals[idx].start <= current_end + B) {
            long long new_start = max(good_intervals[idx].start, current_start + A);
            long long new_end = min(good_intervals[idx].end, current_end + B);

            if (new_start <= new_end) {
                if (next_start == -1) {
                    next_start = new_start;
                    next_end = new_end;
                } else {
                    next_end = max(next_end, new_end);
                }
            }
            if (good_intervals[idx].end > current_end + B) break;
            ++idx;
        }

        if (next_start == -1) {
            cout << "No" << endl;
            return 0;
        }

        current_start = next_start;
        current_end = next_end;

        if (current_end >= N) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

Submission Info

Judge Result