제출 #1305449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305449		vako_p	Port Facility (JOI17_port_facility)	C++20	10 / 100	12 ms	1500 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;

const int mxN = 2e6 + 5;
ll n,mod = 998244353,sz,val[mxN],str[mxN],nd[mxN];
pair<ll,ll> a[mxN];
bool ok = true;

struct ds{
  vector<ll> par;
  vector<vector<ll>> v;
  vector<pair<ll,ll>> lr;

  void init(){
    v.resize(n + 5);
    par.resize(n + 5);
    lr.assign(n + 5, {0, 0});
    for(int i = 0; i < n + 5; i++){
      v[i].pb(i);
      par[i] = 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){
    a = find(a);
    b = find(b);
    if(a == b) return;
    sz--;
    if(v[a].size() < v[b].size()) swap(a, b);
    lr[a].ff = min(lr[a].ff, lr[b].ff);
    lr[a].sd = max(lr[a].sd, lr[b].sd);
    par[b] = a;
    for(auto it : v[b]) 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 val, ll l, ll r, 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(val, l, r, 2 * x + 1, lx, mid);
    set(val, l, r, 2 * x + 2, mid, rx);
  }

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

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

  void find(ll i, vector<ll> &vv){
    find(i, vv, 0, 0, sz);
  }
};

void bfs(ll at, segtree &s){
  queue<ll> q;
  q.push(at);
  while(!q.empty()){
    at = q.front();
    q.pop();
    ll l = a[at].sd,r = a[at].ff;
    vector<ll> v;
    s.find(l, v);
    s.find(r, v);
    for(auto it : v){
      if(val[it]) continue;
      // cout << at << ' ' << a[at].sd << ' ' << a[at].ff << " ---> " << it << ' ' << a[it].sd << ' ' << a[it].ff << endl;
      val[it] = 3 - val[at];
      q.push(it);
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  segtree s;
  ds ss;
  s.init();
  ss.init();
  for(int i = 0; i < n; i++) cin >> a[i].sd >> a[i].ff;
  sort(a, a + n);
  for(int i = 0; i < n; i++) ss.lr[i] = {a[i].sd, a[i].ff};
  sz = n;
  for(int i = 0; i < n; i++){
    ll l = a[i].sd,r = a[i].ff;
    vector<ll> v;
    s.find(l, v);
    for(auto it : v) ss.merge(i, it);
    ll at = ss.find(i);
    s.set(at, ss.lr[at].ff, ss.lr[at].sd + 1);
  }
  ll ans = 1;
  segtree s1;
  s1.init();
  for(int i = 0; i < n; i++) s1.set(i, a[i].sd, a[i].ff + 1);
  ok = false;
  for(int i = n - 1; i >= 0; i--) if(!val[i]){
    val[i] = 1;
    bfs(i, s1);
  } 
  for(int i = 0; i < n; i++){
    // cout << a[i].sd << ' ' << a[i].ff << ' ' << val[i] << '\n';
    str[a[i].sd] = i + 1;
    nd[a[i].ff] = i + 1;
  }
  stack<ll> st[3];
  for(int i = 1; i <= 2 * n; i++){
    // cout << i << ' ' << str[i] << ' ' << nd[i] << endl;
    ll at;
    if(str[i]){
      // cout << " ---> " << i << endl;
      at = str[i] - 1;
      st[val[at]].push(at);
    }
    else{
      at = nd[i] - 1;
      // cout << at << ' ' << val[at] << ' ' << st[val[at]].top() << endl;
      if(st[val[at]].top() != at){
        cout << 0;
        return 0;
      }
      st[val[at]].pop();
    }
  }
  for(int i = 0; i < sz; i++) ans = ans * 2 % mod;
  cout << ans;
}

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