Submission #383891

#	Time	Username	Problem	Language	Result	Execution time	Memory
383891		rama_pang	Port Facility (JOI17_port_facility)	C++14	100 / 100	4871 ms	312600 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

// Assume there is only 1 stack.
// Then all containers' intervals in the stack must be nonintersecting.
// We need to count number of ways to split A[] into 2 subsequences,
// s.t. each subsequence has nonintersecting intervals.
//
// Create an ede (u, v) if interval u and interval v intersects (not overlaps).
// Then, this graph must be bipartite. For each connected component, there are
// 2 ways to put it into A or B. So the answer = 2^{connected components}.
// (0 if the graph is not bipartite).
//
// We can simulate edges with a segment tree and do a DFS. Since we only traverse
// each node once, this runs in O(N log N).

template<typename T>
class SegmentTree {
 public:
  int n;
  T init;
  vector<T> tree;
  function<T(T, T)> f;

  SegmentTree() {}
  SegmentTree(int n, T init, function<T(T, T)> f) : n(n), init(init), tree(2 * n, init), f(f) {}

  void Modify(int p, T x) {
    tree[p += n] = x;
    for (p /= 2; p > 0; p /= 2) {
      tree[p] = f(tree[p * 2], tree[p * 2 + 1]);
    }
  }

  T Query(int l, int r) {
    T res = init;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) res = f(res, tree[l++]);
      if (r & 1) res = f(res, tree[--r]);
    }
    return res;
  }
};

const int MOD = 1e9 + 7;

int N;
vector<pair<int, int>> A;

SegmentTree<pair<int, int>> L; // query maximum, element at L[i] is R[i]
SegmentTree<pair<int, int>> R; // query minimum, element at R[i] is L[i]

void Dfs(int u, int c, vector<int> &colors) {
  if (colors[u] != -1) {
    return;
  }
  colors[u] = c;
  while (true) {
    auto q = L.Query(A[u].first + 1, A[u].second - 1);
    if (A[u].second < q.first) {
      L.Modify(A[q.second].first, L.init);
      Dfs(q.second, 1 - c, colors);
    } else {
      break;
    }
  }
  while (true) {
    auto q = R.Query(A[u].first + 1, A[u].second - 1);
    if (q.first < A[u].first) {
      R.Modify(A[q.second].second, R.init);
      Dfs(q.second, 1 - c, colors);
    } else {
      break;
    }
  }
}

bool NotIntersect(vector<pair<int, int>> ints) {
  vector<int> st;
  sort(begin(ints), end(ints));
  for (auto p : ints) {
    while (!st.empty() && st.back() < p.first) {
      st.pop_back();
    }
    if (!st.empty() && st.back() < p.second) {
      return false;
    }
    st.emplace_back(p.second);
  }
  return true;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;

  L = SegmentTree<pair<int, int>>(2 * N, {-MOD, -MOD}, [&](pair<int, int> a, pair<int, int> b) { return max(a, b); });
  R = SegmentTree<pair<int, int>>(2 * N, {+MOD, +MOD}, [&](pair<int, int> a, pair<int, int> b) { return min(a, b); });

  A.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i].first >> A[i].second;
    A[i].first--, A[i].second--;
    L.Modify(A[i].first, {A[i].second, i});
    R.Modify(A[i].second, {A[i].first, i});
  }

  int ans = 1;
  vector<int> colors(N, -1);
  vector<pair<int, int>> C1, C2;
  for (int i = 0; i < N; i++) {
    if (colors[i] == -1) {
      ans = 2ll * ans % MOD;
      L.Modify(A[i].first, L.init);
      R.Modify(A[i].second, R.init);
      Dfs(i, 0, colors);
    }
  }

  for (int i = 0; i < N; i++) {
    (colors[i] ? C1 : C2).emplace_back(A[i]);
  }

  cout << (NotIntersect(C1) && NotIntersect(C2) ? ans : 0) << '\n';
  return 0;
}

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