Submission #1142184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142184		LucaLucaM	Port Facility (JOI17_port_facility)	C++17	0 / 100	22 ms	47168 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
// acm doar trb sa dau lock in si sa bag jmenu lui voicu
// daca e raspunsu 0 e jover :sob: :pray:
using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int NMAX = 1e6;
const int mod = 1e9 + 7;

std::vector<int> sweep[2 * NMAX + 1];

struct Container {
  int x, y;
  bool operator < (const Container &other) const {
    return x != other.x? x < other.x : y < other.y;
  };
};

Container a[NMAX + 1];

namespace DSU {
  std::vector<int> p;
  std::vector<int> color;

  void init(int n) {
    p.resize(n + 1);
    color.resize(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      p[i] = i;
      color[i] = 0;
    }
  }

  int root(int u) {
    return p[u] == u? u : p[u] = root(p[u]);
  }
  bool join(int u, int v) {
    u = root(u);
    v = root(v);
    if (u != v) {
      p[u] = v;
      if (color[u] == color[v]) {
        color[u] ^= 1;
      }
    } else {
      if (color[u] == color[v]) {
        return false;
      }
    }
    return true;
  }
};

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i].x >> a[i].y;
  }

  std::sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    sweep[a[i].x].push_back(i);
  }

  if (n <= 2000) {
    DSU::init(n);
    for (int i = 1; i < n; i++) {
      for (int j = i + 1; j <= n; j++) {
        if (a[i].y > a[j].x && a[i].y < a[j].y) {
          if (!(DSU::join(i, j))) {
            std::cout << 0;
            return 0;
          }
        }
      }
    } 
    int answer = 1;
    for (int i = 1; i <= n; i++) {
      if (DSU::root(i) == i) {
        answer = answer * 2 % mod;
      }
    }
    std::cout << answer;
    return 0;
  }

  std::vector<int> maxR(2 * n + 1, -1);
  std::vector<int> who(2 * n + 1, -1);

  auto activate = [&](int index) {
    maxR[a[index].x] = a[index].y;
    who[a[index].x] = index;
  };
  auto deactivate = [&](int index) {
    maxR[a[index].x] = -1;
    who[a[index].x] = -1;
  };
  auto query = [&](int l, int r) {
    int maxi = -1, index = -1;
    for (int i = l; i <= r; i++) { 
      if (maxR[i] > maxi) {
        maxi = maxR[i];
        index = who[i];
      }
    }
    return index;
  };

  DSU::init(n);

  int answer = 1;
  for (int L = 2 * n; L > 0; L--) {
    for (const auto &index : sweep[L]) {
      auto [x, y] = a[index];
      int other = query(x, y);
      while (other != -1 && y < a[other].y) {
        // std::cout << "JOIN: " << index << ' ' << other << '\n';
        if (!DSU::join(index, other)) {
          answer = 0;
          break;
        }
        deactivate(other);
        other = query(x, y);
      } 
      activate(index);
    }
  }

  answer = 1;
  for (int i = 1; i <= n; i++) {
    if (DSU::root(i) == i) {
      answer = (2 * answer) % mod;
    }
  }
    
  std::cout << answer;

  return 0;
} 

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22