Решение задачи Точки в отрезках с Codeforces

Без пояснения   Просмотров: 93

Задан набор из n отрезков на оси Ox, каждый отрезок имеет целочисленные координаты концов от 1 до m включительно. Отрезки могут пересекаться, вкладываться или даже совпадать друг с другом. Каждый отрезок характеризуется двумя целыми числами li и ri (1≤li≤ri≤m) — координатами левого и правого концов.

Рассмотрим все целочисленные точки между 1 и m включительно. Ваша задача — вывести все точки из этого множества, не принадлежащие ни одному отрезку. Точка x принадлежит отрезку [l;r] тогда и только тогда, когда l≤x≤r.

Код 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m, a, b;
    cin >> n >> m;
    vector<int> s(m);
    for(int i = 0; i < n; ++i){
        cin >> a >> b;
        for(int j = a - 1; j < b; ++j)
            s[j] = 1;
    }
    vector<int> res;
    for(int i = 0; i < s.size(); ++i)
        if(!s[i])
            res.push_back(i + 1);
    cout << res.size() << endl;
    for(auto i: res)
        cout << i << " ";
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта