Submission #1207908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207908		mychecksedad	Port Facility (JOI17_port_facility)	C++20	0 / 100	94 ms	196160 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;
  Dsu(int n){
    s.resize(n+1, 1);
    p.resize(n+1);
    for(int i = 1; i <= n; ++i){
      p[i] = i;
    }
  }
  int find(int v){
    if(p[v] == v) return v;
    return p[v] = find(p[v]);
  }
  void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b){
      if(s[a] > s[b]) swap(a, b);
      s[b] += s[a];
      p[a] = b;
    }
  }
} d(N);


int 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()) d.merge(T[k][0], v);
    while(T[k].size() > 1){
      d.merge(T[k].back(), T[k][0]);
      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);
}
int check(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return 2;
  if(ql <= l && r <= qr){
    while(T[k].size() > 1){
      if(T[k][0] != T[k].back()){
        return -1;
      }
      T[k].pop_back();
    }
    if(T[k].empty()) return 2;
    return T[k][0];
  }
  int mid = l+r>>1;
  int x = check(l, mid, ql, qr, k<<1);
  int y = check(mid+1, r, ql, qr, k<<1|1);
  if(x == 2) return y;
  if(y == 2) return x;
  if(x == -1 || y == -1) return -1;
  if(x != y) return -1;
  return x;
}
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 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) << ' ';
  // }
  // return;
  for(int i = 1; i <= n*8; ++i) T[i].clear();
  for(int i = 1; i <= n; ++i){
    int ok = check(1, 2*n, a[i][0], a[i][1], 1);
    // cout << ok << ' ' << i << '\n';
    if(ok == -1){
      cout << 0;
      return;
    }
    if(ok == 2) ok = 1;
    add(1, 2*n, a[i][1], 1, 1 - ok);
  }
  ll ans = 1;
  // for(int i = 1; i <= n; ++i){
  //   cerr << d.find(i) << '\n';
  // }
  for(int i = 1; i <= n; ++i){
    if(d.find(i) == i) (ans*=2)%=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();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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