Submission #535742

#	Time	Username	Problem	Language	Result	Execution time	Memory
535742		Soumya1	Port Facility (JOI17_port_facility)	C++17	100 / 100	2359 ms	198788 KiB

port_facility

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mod = 1e9 + 7;
const int mxN = 2e6 + 5;
template<typename T>
struct SegmentTree {
  vector<T> t;
  int n;
  T identity = T();
  SegmentTree() { }
  SegmentTree(int _n) : n(_n) {
    int lg = 31 - __builtin_clz(n);
    if ((1 << lg) < n) lg++;
    lg++;
    t.assign((1 << lg) + 5, identity);
  }
  void update(int x, int lx, int rx, int p, T v) {
    if (lx == rx) {
      t[x] = v;
      return;
    }
    int mx = (lx + rx) >> 1;
    if (p <= mx) update(x << 1, lx, mx, p, v);
    else update(x << 1 | 1, mx + 1, rx, p, v);
    t[x] = merge(t[x << 1], t[x << 1 | 1]);
  }
  void update(int p, T v) {
    update(1, 1, n, p, v);
  }
  T query(int x, int lx, int rx, int l, int r) {
    if (lx > r || l > rx) return identity;
    if (l <= lx && r >= rx) return t[x];
    int mx = (lx + rx) >> 1;
    return merge(query(x << 1, lx, mx, l, r), query(x << 1 | 1, mx + 1, rx, l, r));
  }
  T query(int l, int r) {
    return query(1, 1, n, l, r);
  }
};
struct Min {
  int m = 1e9;
  Min() { m = 1e9; }
  Min(int _m) { m = _m; }
  friend Min merge(Min a, Min b) { return Min(min(a.m, b.m)); }
};
struct Max {
  int m = 0;
  Max() { m = 0; }
  Max(int _m) { m = _m; }
  friend Max merge(Max a, Max b) { return Max(max(a.m, b.m)); }
};
SegmentTree<Min> st1;
SegmentTree<Max> st2;
vector<pair<int, int>> a;
int who[mxN];
int c[mxN];
bool vis[mxN];
void dfs(int i) {
  vis[i] = true;
  st1.update(a[i].second, Min(1e9));
  st2.update(a[i].first, Max(0));
  int j = st1.query(a[i].first, a[i].second).m;
  while (j < a[i].first) {
    c[who[j]] = c[i] ^ 1;
    dfs(who[j]);
    j = st1.query(a[i].first, a[i].second).m;
  }
  j = st2.query(a[i].first, a[i].second).m;
  while (j > a[i].second) {
    c[who[j]] = c[i] ^ 1;
    dfs(who[j]);
    j = st2.query(a[i].first, a[i].second).m;
  }
}
void testCase() {
  int n;
  cin >> n;
  a.resize(n);
  for (auto &[x, y] : a) cin >> x >> y;
  sort(a.begin(), a.end());
  st1 = SegmentTree<Min> (2 * n);
  st2 = SegmentTree<Max> (2 * n);
  for (auto [x, y] : a) {
    st1.update(y, Min(x));
    st2.update(x, Max(y));
  }
  for (int i = 0; i < n; i++) {
    who[a[i].first] = who[a[i].second] = i;
  }
  int ans = 1;
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      ans += ans;
      if (ans >= mod) ans -= mod;
      dfs(i);
    }
  }
  {
    for (int col : {0, 1}) {
      set<int> s;
      for (int i = 0; i < n; i++) {
        if (c[i] != col) continue;
        auto it = s.lower_bound(a[i].first);
        if (it != s.end() && *it < a[i].second) {
          cout << "0\n";
          return;
        }
        s.insert(a[i].second);
      }
    }
  }
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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