Submission #203729

#	Time	Username	Problem	Language	Result	Execution time	Memory
203729		EntityIT	Port Facility (JOI17_port_facility)	C++14	78 / 100	6004 ms	364864 KiB

port_facility

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

const int mod = 1e9 + 7;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );
struct Mint {
  int a;
  Mint(int _a = 0) : a(_a) {}
  friend ostream& operator << (ostream &out, const Mint &_) {
    out << _.a;
    return out;
  }

  bool operator == (const Mint &_) const { return a == _.a; }
  bool operator ! () const { return !a; }

  Mint operator + (const Mint &_) const {
    int ret = a + _.a;
    return ret < mod ? Mint(ret) : Mint(ret - mod);
  }
  Mint operator - (const Mint &_) const { return *this + Mint(mod - _.a); }
  Mint operator * (const Mint &_) const { return Mint( (int)( (LL)a * _.a % mod) ); }
  friend Mint& operator += (Mint &a, const Mint &b) { return a = a + b; }
  friend Mint& operator -= (Mint &a, const Mint &b) { return a = a - b; }
  friend Mint& operator *= (Mint &a, const Mint &b) { return a = a * b; }
  Mint& operator ++ () { return *this = *this + Mint(1); }
  Mint& operator -- () { return *this = *this - Mint(1); }

  template<class T> Mint binPow(T exp) const {
    Mint ret(1), c = *this;
    for (; exp; exp >>= 1, c *= c) if (exp & 1) ret *= c;
    return ret;
  }
};

int n;
vector<pair<int, int> > container;

struct Dsu {
  vector<int> pSet;
  Dsu(int nSet = 0) { pSet.assign(nSet, 0); iota(all(pSet), 0); }
  void reset(int nSet = 0) { pSet.assign(nSet, 0); iota(all(pSet), 0); }

  int findSet(int i) { return i == pSet[i] ? i : pSet[i] = findSet(pSet[i]); }
  bool unite(int i, int j) {
    i = findSet(i); j = findSet(j);
    if (i == j) return false;
    pSet[i] = j;
    return true;
  }
} dsu;

vector<int> idx;
vector<vector<pair<int, bool> > > gr;
struct It {
  #define lC (i << 1)
  #define rC (i << 1 | 1)
  #define Mid ( (Left + Right) >> 1)
  #define rt int i = 1, int Left = 0, int Right = n - 1

  vector<vector<int> > group;
  vector<int> iGroup;
  It(int nNode) { group.assign(nNode, {} ); iGroup.assign(nNode, 0); }

  void ins(int pos, int id, rt) {
    group[i].emplace_back(id);
    if (Left == Right) return;
    if (pos <= Mid) ins(pos, id, lC, Left, Mid);
    else ins(pos, id, rC, Mid + 1, Right);
  }

  void addEdge(int l, int r, int id, rt) {
    if (l <= Left && Right <= r) {
      while (iGroup[i] < sz(group[i]) && container[ group[i][ iGroup[i] ] ].first < container[id].first) {
        if (iGroup[i]) {
          if (dsu.unite(group[i][ iGroup[i] ], group[i][ iGroup[i] - 1 ]) ) {
            gr[ group[i][ iGroup[i] ] ].emplace_back(group[i][ iGroup[i] - 1 ], false);
            gr[ group[i][ iGroup[i] - 1 ] ].emplace_back(group[i][ iGroup[i] ], false);
          }
        }
        ++iGroup[i];
      }
      if (iGroup[i]) {
        if (dsu.unite(id, group[i][ iGroup[i] - 1 ]) ) {
          gr[id].emplace_back(group[i][ iGroup[i] - 1 ], true);
          gr[group[i][ iGroup[i] - 1 ]].emplace_back(id, true);
        }
      }
      return;
    }
    if (l <= Mid) addEdge(l, r, id, lC, Left, Mid);
    if (Mid < r) addEdge(l, r, id, rC, Mid + 1, Right);
  }
};

vector<int> label;
void dfs(int u, int cur) {
  label[u] = cur;
  for (auto e : gr[u]) {
    int v = e.first; bool w = e.second;
    if (!(~label[v]) ) dfs(v, cur ^ w);
  }
}

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

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  cin >> n;
  container.assign(n, {} );
  for (int i = 0; i < n; ++i) {
      cin >> container[i].first >> container[i].second;
    --container[i].first; --container[i].second;
  }
  vector<pair<int, bool> > change(n << 1);
  for (int i = 0; i < n; ++i) {
    change[ container[i].first ] = { i, true };
    change[ container[i].second ] = { i, false };
  }
  idx.assign(n << 1, -1);
  for (int i = 0, cur = 0; i < n << 1; ++i) {
    idx[i] = cur;
    cur += !change[i].second;
  }

  vector<int> sor(n); iota(all(sor), 0);
  sort(all(sor), [&](int i, int j) { return container[i].first < container[j].first; });
  It it( (n + 5) << 2);
  for (auto i : sor) it.ins(idx[ container[i].second ], i);

  dsu.reset(n);
  gr.assign(n, {} );
  for (auto i : sor) it.addEdge(idx[ container[i].first ], idx[ container[i].second ], i);

  Mint ans(1);
  label.assign(n, -1);
  for (int u = 0; u < n; ++u) if (!(~label[u]) ) {
    dfs(u, 0);
    ans += ans;
  }

  stack<int> st[2];
  for (auto _ : change) {
    int i = _.first; bool in = _.second;
    if (in) st[ label[i] ].emplace(i);
    else {
      if (st[ label[i] ].top() ^ i) {
        ans = Mint(0);
        break ;
      }
      else st[ label[i] ].pop();
    }
  }

  cout << ans << '\n';

  return 0;
}

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