Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- // Решение задачи с уникальными отрезками за O(N)
- int max(int a, int b) {
- if (a > b){
- return a;
- } else {
- return b;
- }
- }
- int min(int a, int b) {
- if (a < b){
- return a;
- } else {
- return b;
- }
- }
- int main() {
- int N;
- std::cin >> N;
- int* a = new int[N];
- int* b = new int[N];
- int* C = new int[N]; // Тут храним начала циклов
- int* D = new int[N]; // Тут концы циклов
- // Заполняем нулями
- for (int i = 0; i < N; ++i) {
- C[i] = 0;
- D[i] = 0;
- }
- // Заполняем значениями
- for (int i = 0; i < N; ++i) {
- std::cin >> a[i] >> b[i];
- }
- // Здесь записываем границы
- for (int i = 0; i < N; ++i) {
- if (a[i] != b[i]) {
- C[i] = min(a[i], b[i]);
- D[i] = max(a[i], b[i]);
- }
- }
- // Для хранения непересечений
- int notIntersect = 0;
- // За линейное ищем непересекающиеся - если по индексам нули в массивах границ, если не входят в границы!
- for (int i = 0; i < N; ++i) {
- if (a[i] == b[i] && D[i] == 0 && C[i] == 0){
- if (a[i] && b[i] < min(C[i], D[i]) || a[i] && b[i] > min(C[i], D[i])){
- notIntersect++;
- }
- }
- }
- // Выводим значение
- cout << notIntersect;
- delete[] a;
- delete[] b;
- delete[] C;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
