Submission #718434

#	Time	Username	Problem	Language	Result	Execution time	Memory
718434		cig32	Port Facility (JOI17_port_facility)	C++17	100 / 100	2345 ms	298776 KiB

port_facility

#include "bits/stdc++.h"
#define int long long

using namespace std;

const int MAXN = 1e6 + 10;

const int MOD = 1e9 + 7;

pair<int,int> p[MAXN];
int n;

stack<int> stka, stkb;
set<int> fin;

int dsu[MAXN];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}

void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}

int trigger[2*MAXN];

struct segtree_min {

  vector<pair<int, int> > st;
  int stok;

  void u(int l, int r, int tar, int idx, int val1, int val2) {
    if(l == r) {
      st[idx] = {val1, val2};
      return;
    }
    int mid = (l + r) >> 1;
    if(tar <= mid) u(l, mid, tar, 2*idx+1, val1, val2);
    else u(mid+1, r, tar, 2*idx+2, val1, val2);
    st[idx] = min(st[2*idx+1], st[2*idx+2]);
  }

  pair<int,int> qu(int l, int r, int constl, int constr, int idx) {
    if(l <= constl && constr <= r) return st[idx];
    int mid = (constl+constr) >> 1;
    if(mid<l || r <constl) return qu(l, r, mid+1, constr, 2*idx+2);
    else if(constr<l || r<mid+1) return qu(l, r, constl, mid, 2*idx+1);
    else {
      return min(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
    }
  }

  void resize(int k) {
    stok = k;
    st.resize(4*k + 10);
  }
  void upd(int i, int v1, int v2) {
    u(1, stok, i, 0, v1, v2);
  }
  pair<int,int> range_min(int l, int r) {
    return qu(l, r, 1, stok, 0);
  }
};

vector<int > adj[MAXN];
char c[MAXN];
bool vis[MAXN];
void dfs(int node) {
  vis[node] = 1;
  for(int x: adj[node]) {
    if(!vis[x]) {
      c[x] = (c[node] == 'A' ? 'B' : 'A');
      dfs(x);
    }
  }
}


int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i=1; i<=n; i++) {
    cin >> p[i].first >> p[i].second;
  }
  sort(p+1, p+1+n);
  
  
  for(int i=1; i<=n; i++) dsu[i] = i;
  for(int i=1; i<=n; i++) trigger[p[i].second] = i;
  segtree_min stm;
  stm.resize(2*n);
  for(int i=1; i<=2*n; i++) stm.upd(i, 1e9, 0);
  for(int i=1; i<=2*n; i++) {
    if(trigger[i]) {
      int l = p[trigger[i]].first, r = p[trigger[i]].second; // query [l, r]
      pair<int,int> res = stm.range_min(l, r);
      if(res.second != 0 && res.first < l) {
        union_(res.second, trigger[i]);
        adj[res.second].push_back(trigger[i]);
        adj[trigger[i]].push_back(res.second);
      }
      stm.upd(i, l, trigger[i]);
    }
  }
  for(int i=1; i<=2*n; i++) trigger[i] = 0;
  for(int i=1; i<=n; i++) trigger[p[i].first] = i;
  for(int i=1; i<=2*n; i++) stm.upd(i, 1e9, 0);
  for(int i=2*n; i>=1; i--) {
    if(trigger[i]) {
      int l = p[trigger[i]].first, r = p[trigger[i]].second; // query [l, r]
      pair<int,int> res = stm.range_min(l, r);
      if(res.second != 0 && res.first < -r) {
        union_(res.second, trigger[i]);
        adj[res.second].push_back(trigger[i]);
        adj[trigger[i]].push_back(res.second);
      }
      stm.upd(i, -r, trigger[i]);
    }
  }
  
  for(int i=1; i<=n; i++) {
    if(!vis[i]) {
      c[i] = 'A';
      dfs(i);
    }
  }

  for(int i=1; i<=n; i++) {
    while(stka.size() && stka.top() < p[i].first) stka.pop();
    while(stkb.size() && stkb.top() < p[i].first) stkb.pop();
    int alim = (stka.size() ? stka.top() : 1e9);
    int blim = (stkb.size() ? stkb.top() : 1e9);
    if(c[i] == 'A') {
      if(alim < p[i].second) return cout << "0\n", 0;
      stka.push(p[i].second);
    }
    else {
      if(blim < p[i].second) return cout << "0\n", 0;
      stkb.push(p[i].second);
    }
  }
  int ans = 1;
  for(int i=1; i<=n; i++) fin.insert(set_of(i));
  int len = fin.size();
  for(int i=0; i<len; i++) ans = (ans*2) % MOD;
  cout << ans << "\n";
}
/*
6
2 8
6 12
1 9
4 7
10 11
3 5

7
8 12
2 10
5 7
11 14
1 3
4 13
6 9
*/

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