Submission #244150

#TimeUsernameProblemLanguageResultExecution timeMemory
244150AlexPop28Port Facility (JOI17_port_facility)C++11
78 / 100
6098 ms540776 KiB
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int MOD = (int)1e9 + 7;

template<class T, class F = function<T(const T&, const T&)>>
struct SegmTree {
  int n;
  T def;
  F f;
  vector<T> t;
  SegmTree(int n_, T def_, F f_) : n(n_), def(def_), f(f_), t(4 * n, def) {}

  void Update(int node, int left, int right, int pos, T val) {
    if (pos < left || pos > right) return;
    if (left == right) {
      t[node] = val;
      return;
    }
    int mid = left + (right - left) / 2;
    Update(2 * node + 1, left, mid, pos, val);
    Update(2 * node + 2, mid + 1, right, pos, val);
    t[node] = f(t[2 * node + 1], t[2 * node + 2]);
  }

  T Query(int node, int left, int right, int x, int y) {
    if (right < x || y < left) return def;
    if (x <= left && right <= y) {
      return t[node];
    }
    int mid = left + (right - left) / 2;
    return f(Query(2 * node + 1, left, mid, x, y),
             Query(2 * node + 2, mid + 1, right, x, y));
  }

  void Update(int pos, T val) {
    Update(0, 0, n - 1, pos, val);
  }

  T Query(int l, int r) {
    if (l > r) return def;
    return Query(0, 0, n - 1, l, r);
  }
};

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

  int n; cin >> n;  
  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; ++i) {
    int x, y; cin >> x >> y; --x, --y;
    v[i] = {x, y};
  }

  SegmTree<pair<int, int>> beg(2 * n, {2 * n, 2 * n},
    [](pair<int, int> a, pair<int, int> b) {
      return min(a, b);
    });

  SegmTree<pair<int, int>> fin(2 * n, {-1, -1},
    [](pair<int, int> a, pair<int, int> b) {
      return max(a, b);
    });

  for (int i = 0; i < n; ++i) {
    fin.Update(v[i].first, {v[i].second, i});
    beg.Update(v[i].second, {v[i].first, i});
  }

  vector<int> color(n, -1);

  function<void(int, int)> DFS = [&](int node, int col) {
    color[node] = col;
    fin.Update(v[node].first, {-1, -1});
    beg.Update(v[node].second, {2 * n, 2 * n});

    while (true) {
      auto p = fin.Query(v[node].first + 1, v[node].second - 1);
      if (p.first < v[node].second) break;
      DFS(p.second, 1 ^ col);
    }
    while (true) {
      auto p = beg.Query(v[node].first + 1, v[node].second - 1);
      if (p.first > v[node].first) break;
      DFS(p.second, 1 ^ col);
    }
  };

  int ans = 1;
  for (int i = 0; i < n; ++i) {
    if (color[i] == -1) {
      ans += ans;
      if (ans >= MOD) ans -= MOD;
      DFS(i, 0);
    }
  }

  vector<int> events(2 * n);
  for (int i = 0; i < n; ++i) {
    events[v[i].first] = i;
    events[v[i].second] = ~i;
  }

  vector<vector<int>> stacks(2);
  for (int node : events) {
    auto &stk = stacks[color[node < 0 ? ~node : node]];
    if (node >= 0) {
      stk.emplace_back(node); 
    } else {
      node = ~node;
      if (!stk.empty() && stk.back() == node) stk.pop_back();
    }
  }

  if (stacks[0].empty() && stacks[1].empty()) {
    cout << ans << endl;
  } else {
    cout << 0 << endl;
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...