Submission #244158

#	Time	Username	Problem	Language	Result	Execution time	Memory
244158		AlexPop28	Port Facility (JOI17_port_facility)	C++11	100 / 100	4161 ms	227504 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_), t(2 * n, def) {}

  void Update(int pos, T val) {
    t[pos += n] = val;
    while (pos) {
      pos /= 2;
      t[pos] = f(t[2 * pos], t[2 * pos + 1]);
    }
  }

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

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: 22 / 22