Advertisement
coloriot

HA20_2

Aug 24th, 2024
20
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // Решение задачи с уникальными отрезками за O(N)
  6.  
  7. int max(int a, int b) {
  8.     if (a > b){
  9.         return a;
  10.     } else {
  11.         return b;
  12.     }
  13. }
  14.  
  15. int min(int a, int b) {
  16.     if (a < b){
  17.         return a;
  18.     } else {
  19.         return b;
  20.     }
  21. }
  22.  
  23.  
  24. int main() {
  25.     int N;
  26.     std::cin >> N;
  27.  
  28.     int* a = new int[N];
  29.     int* b = new int[N];
  30.     int* C = new int[N]; // Тут храним начала циклов
  31.     int* D = new int[N]; // Тут концы циклов
  32.  
  33.     // Заполняем нулями
  34.     for (int i = 0; i < N; ++i) {
  35.         C[i] = 0;
  36.         D[i] = 0;
  37.     }
  38.  
  39.     // Заполняем значениями
  40.     for (int i = 0; i < N; ++i) {
  41.         std::cin >> a[i] >> b[i];
  42.     }
  43.  
  44.     // Здесь записываем границы
  45.     for (int i = 0; i < N; ++i) {
  46.         if (a[i] != b[i]) {
  47.             C[i] = min(a[i], b[i]);
  48.             D[i] = max(a[i], b[i]);
  49.         }
  50.     }
  51.  
  52.     // Для хранения непересечений
  53.     int notIntersect = 0;
  54.    
  55.     // За линейное ищем непересекающиеся - если по индексам нули в массивах границ, если не входят в границы!
  56.     for (int i = 0; i < N; ++i) {
  57.         if (a[i] == b[i] && D[i] == 0 && C[i] == 0){
  58.             if (a[i] && b[i] < min(C[i], D[i]) || a[i] && b[i] > min(C[i], D[i])){
  59.                 notIntersect++;
  60.             }
  61.         }
  62.     }
  63.    
  64.     // Выводим значение
  65.     cout << notIntersect;
  66.  
  67.     delete[] a;
  68.     delete[] b;
  69.     delete[] C;
  70.  
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement