제출 #244154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
244154		AlexPop28	Port Facility (JOI17_port_facility)	C++11	78 / 100	6101 ms	546156 KiB

port_facility

#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_) {
    int sz = 1;
    while (sz < n) sz <<= 1;
    t.resize(2 * sz, 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;
    if (pos <= mid)
      Update(2 * node + 1, left, mid, pos, val);
    else
      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 (x <= left && right <= y) {
      return t[node];
    }
    int mid = left + (right - left) / 2;
    T ret = def;
    if (x <= mid)
      ret = f(ret, Query(2 * node + 1, left, mid, x, y));
    if (mid < y)
      ret = f(ret, Query(2 * node + 2, mid + 1, right, x, y));
    return ret; 
  }

  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;
  }
}

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