Точки и отрезки

@H4msterid · Регистрация: 27.01.2022

Author24 — интернет-сервис помощи студентам

Всем привет, первый раз на форуме, если сообщение будет плохо отображаться, прошу простить.
Вот задачка:

Дано n отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам она принадлежит. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a,b) <= x <= max(a,b).

Входные данные
Первая строка содержит два целых числа n (1 <= n <= 30000) — число отрезков и m (1 <= m <= 30000) — число точек. В следующих n строках записаны по два целых числа a_i и b_i — координаты концов соответствующего отрезка. В последней строке записаны m целых чисел — координаты точек.
Все числа во входном файле не превосходят по модулю 10⁹.

Выходные данные
Программа должна вывести m чисел — для каждой точки выведите количество отрезков, в которых она содержится.

ПРИМЕР
Ввод:

2 2
0 5
10 7
1 6

Вывод:

1 0

--------------------------------------
Ввод:

1 3
-10 10
-100 100 0

Вывод:

0 0 1

Моё решение проходит только первые несколько тестов. Помогите, пожалуйста понять, что не так.

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
struct Event {
    ll x, type, num;    // 0 - open, 1 - point, 2 - close
    Event(ll x, ll type, ll num) : x(x), type(type), num(num) {};
};
 
bool operator <(const Event& a, const Event& b) {   // В одной координате
    return make_pair(a.x, a.type) < make_pair(b.x, b.type); // Сначала обрабатывается открытие отрезка, потом точка, потом закрытие отрезка
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<Event> ev;
    ev.reserve(n + m);
    int l, r;
    for (int i = 0; i < n; ++i) {
        cin >> l >> r;
        ev.push_back(Event(l, 0, -1));
        ev.push_back(Event(r, 2, -1));
    }
    for (int i = 0; i < m; ++i) {
        cin >> l;
        ev.push_back(Event(l, 1, i));
    }
    sort(ev.begin(), ev.end());
    int bal = 0;        // Кол-во "активных отрезков"
    vector<int> ans(m);
    for (auto& e : ev) {
        if (e.type == 0) ++bal;
        else if (e.type == 1) ans[e.num] = bal;
        else --bal;
    }
    for (auto i : ans) {
        cout << i << ' ';
    }
    cout << '\n';
    return 0;
}

@DeCrinal · 28.01.2022, 11:47

Когда-то писал решение этой задачи
Попробуйте:

C++

#include <iostream>
#include<ios>
#include<algorithm>
#include<limits>
#include<vector>
using namespace std;
bool cmp1(pair<pair<int,int>,int>&val1,pair<pair<int,int>,int>&val2){
    if(val1.first.first<val2.first.first)
        return true;
    else{
        if(val1.first.first==val2.first.first){
            if(val1.first.second==1&&val2.first.second!=1)
                return true;
            if(val1.first.second==0&&val2.first.second==-1)
                return true;
            if(val1.first.second==0&&val2.first.second==1)
                return false;
        }
    }
    return false;
}
bool cmp2(pair<pair<int,int>,int>&val1,pair<pair<int,int>,int>&val2){
    return val1.second<val2.second;
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    int  n, m;
    int input;
    cin>>n>>m;
    vector<pair<pair<int,int>,int>>A;
    for(int i = 0;i<n;i++){
       cin>>input;
       A.push_back(make_pair(make_pair(input,1),INT32_MAX));
       cin>>input;
       A.push_back(make_pair(make_pair(input,-1),INT32_MAX));
    }
    for(int i = 0; i<m;i++){
        cin>>input;
        A.push_back(make_pair(make_pair(input,0),i));
    }
    sort(A.begin(),A.end(),cmp1);
    /*for(unsigned int i = 0; i<A.size();i++){
        cout<<A[i].first.first<<" "<<A[i].first.second<<endl;
    }*/
    int sum=0;
    int N = 2*n+m;
    for(int i = 0; i<N;i++){
        if(A[i].first.second==1){
           sum++;
        }else if(A[i].first.second==-1){
            sum--;
        }
        else{
            A[i].first.second=sum;
        }
    }
    sort(A.begin(),A.end(),cmp2);
    for(int i = 0; i<m;i++){
        cout<<A[i].first.second<<" ";
    }
    return 0;
}

Тут подразумевается, что координаты концов прямой вводятся в правильном порядке. Можете добавить дополнительную проверку, если тесты подразумевают возможность неправильного ввода

@H4msterid · 28.01.2022, 15:42 **[ТС]**

Проходит такие же тесты как и моё

Добавлено через 11 минут
Я понял в чём дело! Дело чисто в невнимательности. В моём условии сказано, "если выполняется двойное неравенство min(a,b) <= x <= max(a,b)", то есть координаты начала и конца необязательно отрезка задаются по возрастанию. Поэтому начало отрезка это min(из двух точек), а конец - это max(из двух точек)!!!

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
struct Event {
    ll x, type, num;    // 0 - open, 1 - point, 2 - close
    Event(ll x, ll type, ll num) : x(x), type(type), num(num) {};
};
 
bool operator <(const Event& a, const Event& b) {   // В одной координате
    return make_pair(a.x, a.type) < make_pair(b.x, b.type); // Сначала обраюатывается открытие отрезка, потом точка, потом закрытие отрезка
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<Event> ev;
    ev.reserve(n + m);
    int l, r;
    for (int i = 0; i < n; ++i) {
        cin >> l >> r;
        ev.push_back(Event(min(l, r), 0, -1));      // !!!!
        ev.push_back(Event(max(l, r), 2, -1));  // !!!!
    }
    for (int i = 0; i < m; ++i) {
        cin >> l;
        ev.push_back(Event(l, 1, i));
    }
    sort(ev.begin(), ev.end());
    int bal = 0;        // Кол-во "активных отрезков"
    vector<int> ans(m);
    for (auto& e : ev) {
        if (e.type == 0) ++bal;
        else if (e.type == 1) ans[e.num] = bal;
        else --bal;
    }
    for (int i = 0; i < m; ++i) {
        cout << ans[i] << ' ';
    }
    return 0;
}

Теперь заходит на 100

@Иван228282 · 23.09.2023, 23:25

ахаха, то же самое было, а я сижу голову ломаю над событиями)

@Kuzia domovenok · 24.09.2023, 21:44

Иван228282, вы из одной школы?

@KSergey9 · 25.09.2023, 12:03

Не по теме:

Сообщение от H4msterid

то есть координаты начала и конца необязательно отрезка задаются по возрастанию.

Но ведь такой вариант есть даже в приведенном здесь примере входных.
Выходит, вы даже не проверили на известных данных корректность работы программы, а сразу запустили тесты? Грустно, товарищи!

@Иван228282 0 / 0 / 0 Регистрация: 27.09.2021 Сообщений: 9
	23.09.2023, 23:25	4
	ахаха, то же самое было, а я сижу голову ломаю над событиями) 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,495 Записей в блоге: 1
	24.09.2023, 21:44	5
	Иван228282, вы из одной школы? 0

@KSergey9
	25.09.2023, 12:03 Точки и отрезки #6
	Не по теме: Сообщение от H4msterid то есть координаты начала и конца необязательно отрезка задаются по возрастанию. Но ведь такой вариант есть даже в приведенном здесь примере входных. Выходит, вы даже не проверили на известных данных корректность работы программы, а сразу запустили тесты? Грустно, товарищи! 0