Submission #1299253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299253		vako_p	Port Facility (JOI17_port_facility)	C++20	22 / 100	6095 ms	38860 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " -----> " << x << endl;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int mxN = 1e6 + 5;
ll n,mod = 1e9 + 7,val[mxN];
pair<ll,ll> a[mxN];

struct ds{
  vector<ll> par,rank;
  vector<vector<ll>> v;
  ll sz;
 
  void init(){
    sz = n;
    par.resize(n + 1);
    rank.assign(n + 1, 0LL);
    v.resize(n + 1);
    for(int i = 1; i <= n; i++){
      par[i] = i;
      v[i].pb(i);
    }
  }

  ll find(ll at){
    if(par[at] == at) return at;
    par[at] = find(par[at]);
    return par[at];
  }

  void merge(ll a, ll b){
    bool ok = (val[a] == val[b]);
    a = find(a);
    b = find(b);
    if(a == b){
      if(ok){
        cout << 0;
        exit(0);
      }
      return;
    }
    sz--;
    if(rank[a] < rank[b]) swap(a, b);
    par[b] = a;
    rank[a] += (rank[a] == rank[b]);
    if(v[a].size() > v[b].size()) swap(v[a], v[b]);
    for(auto it : v[b]){
      if(ok) val[it] = 1 - val[it]; 
      v[a].pb(it);
    }
    v[b].clear();
v[b].shrink_to_fit();
  }
};

struct segtree{
  vector<vector<ll>> v;
  ll sz = 1;

  void init(){
    while(sz < 2 * n + 5) sz *= 2;
    v.resize(2 * sz);
  }

  void set(ll l, ll r, ll val, ll x, ll lx, ll rx){
    if(lx >= r or rx <= l) return;
    if(lx >= l and rx <= r){
      v[x].pb(val);
      return;
    }
    ll mid = lx + (rx - lx) / 2;
    set(l, r, val, 2 * x + 1, lx, mid);
    set(l, r, val, 2 * x + 2, mid, rx);
  }

  void set(ll l, ll r, ll val){
    set(l, r, val, 0, 0, sz);
  }

  void find(ll i, vector<ll> &res, ll x, ll lx, ll rx){
    for(auto it : v[x]) res.pb(it);
    if(rx - lx == 1) return;
    ll mid = lx + (rx - lx) / 2;
    if(i < mid) find(i, res, 2 * x + 1, lx, mid);   
    else find(i, res, 2 * x + 2, mid, rx);
  }

  vector<ll> find(ll i){
    vector<ll> res;
    find(i, res, 0, 0, sz);
    return res;
  }
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  cin >> n; 
  for(int i = 1; i <= n; i++) cin >> a[i].ff >> a[i].sd;
  segtree s;
  s.init();
  ds ss;
  ss.init();
  sort(a + 1, a + n + 1);
  ll ans = 1;
  for(int i = n; i >= 1; i--){
    vector<ll> v = s.find(a[i].sd);
    val[i] = 1;
    for(auto it : v) ss.merge(i, it);
    // for(auto it : v) cout << i << ' ' << it << '\n';
    if(a[i - 1].ff != a[i].ff){
      for(int j = i; j <= n and a[j].ff == a[i].ff; j++) s.set(a[j].ff + 1, a[j].sd, j);
    }
  }
  for(int i = 0; i < ss.sz; i++) ans = ans * 2 % mod;
  cout << ans;
}

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