Submission #1207922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207922		mychecksedad	Port Facility (JOI17_port_facility)	C++20	100 / 100	2327 ms	412952 KiB

port_facility

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

struct Dsu{
  vector<int> p, s, sw;
  Dsu(int n){
    s.resize(n+1, 1);
    p.resize(n+1);
    sw.resize(n+1);
    for(int i = 1; i <= n; ++i){
      p[i] = i;
    }
  }
  int find(int v){
    if(p[v] == v) return v;
    return find(p[v]);
  }
  bool col(int v){
    if(p[v] == v) return 0;
    return col(p[v]) ^ sw[v];
  }
  void merge(int u, int v){
    if(u == v) return;
    int cl = col(u), clv = col(v);
    int a = find(u);
    int b = find(v);
    if(a != b){
      if(s[a] > s[b]) swap(a, b);
      s[b] += s[a];
      p[a] = b;
      if(cl == clv) sw[a] = 1;
      else sw[a] = 0;
    }
  }
} d(N);


int n, TT[8*N];
array<int, 2> a[N];
vi T[8*N];
void merg(int l, int r, int ql, int qr, int k, int v){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    // cerr << "merge: " << l << ' ' << r << '\n';
    // if(T[k].size()){
    //   cerr << d.col(T[k][0]) << ' ' << d.col(v) << '\n';
    //   cerr << T[k][0] << ' ' << v << '\n';
    // }
    if(T[k].size()){
      d.merge(T[k][0], v);
    }
    while(T[k].size() > 1){
      d.merge(T[k].back(), v);
      T[k].pop_back();
    }
    return;
  }
  int mid = l+r>>1;
  merg(l, mid, ql, qr, k<<1, v);
  merg(mid+1, r, ql, qr, k<<1|1, v);
}
void check(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    // cerr << l << ' ' << r << ' ' << TT[k] << '\n';
    if(TT[k]){
      cout << 0;
      exit(0);
    }
    return;
  }
  int mid = l+r>>1;
  check(l, mid, ql, qr, k<<1);
  check(mid+1, r, ql, qr, k<<1|1);
}
void add(int l, int r, int p, int k, int v){
  T[k].pb(v);
  // cerr << l << ' ' << r << ' ' << v << '\n';
  if(l == r){
    return;
  }
  int mid = l+r>>1;
  if(p <= mid) add(l, mid, p, k<<1, v);
  else add(mid+1, r, p, k<<1|1, v);
}

void add2(int l, int r, int p, int k, int v){
  TT[k]++;
  // cerr << l << ' ' << r  << '\n';
  if(l == r){
    return;
  }
  int mid = l+r>>1;
  if(p <= mid) add2(l, mid, p, k<<1, v);
  else add2(mid+1, r, p, k<<1|1, v);
}
void solve(){
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i][0] >> a[i][1];
  }
  sort(a+1, a+1+n);
  for(int i = 1; i <= n; ++i){
    add(1, n*2, a[i][1], 1, i);
    merg(1, n*2, a[i][0], a[i][1], 1, i);
  }

  // for(int i = 1; i <= n; ++i){
  //   cout << d.find(i) << ' ';
  // }
  // en;
  // for(int i = 1; i <= n; ++i){
  //   cout << d.col(i) << ' ';
  // }
  // en;

  for(int rep = 0; rep < 2; ++rep){
    for(int i = 1; i <= n*8; ++i){
      TT[i] = 0;
    }

    for(int i = 1; i <= n; ++i){
      if(d.col(i) == rep){
        check(1, n*2, a[i][0], a[i][1], 1);
        add2(1, 2*n, a[i][1], 1, i);
      }
    }
  }
  ll ans = 1;
  for(int i = 1; i <= n; ++i){
    if(d.find(i) == i) ans = 2*ans % MOD;
  }
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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