Submission #1170604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170604		Zero_OP	Port Facility (JOI17_port_facility)	C++20	78 / 100	277 ms	82472 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl =pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;

using vpi = vector<pi>;
using vpl = vector<pl>;

//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().cout());
//ll random(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); }

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
      if(fopen("B.inp", "r")){
            freopen("B.inp", "r", stdin);
            freopen("B.out", "w", stdout);
      }
}

const int MAX = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9;

int N, l[MAX], r[MAX], inv_from_l[MAX], inv_from_r[MAX], color[MAX];

struct DSU{
      int components;
      vi lab;
      DSU(int n) : lab(n, -1), components(n) {}

      int root(int u){
            return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
      }

      bool join(int u, int v){
            u = root(u); v = root(v);
            if(u == v) return false;
            if(lab[u] > lab[v]) swap(u, v);
            lab[u] += lab[v]; lab[v] = u; --components;
            return true;
      }
};

struct SegmentTreeMax{
      vi st;
      int n;
      SegmentTreeMax(int n) : n(n), st(n << 2, -inf) {}

      void update(int id, int val){
            id += n;
            st[id] = val;
            for(; id > 1; id >>= 1) st[id >> 1] = max(st[id], st[id^1]);
      }

      int query(int l, int r){
            int mx = -inf;
            l += n; r += n+1;
            for(; l < r; l >>= 1, r >>= 1){
                  if(l&1){
                        maximize(mx, st[l++]);
                  }

                  if(r&1){
                        maximize(mx, st[--r]);
                  }
            }
            return mx;
      }
};

struct SegmentTreeMin{
      vi st;
      int n;
      SegmentTreeMin(int n) : n(n), st(n << 2, inf) {}

      void update(int id, int val){
            id += n;
            st[id] = val;
            for(; id > 1; id >>= 1) st[id >> 1] = min(st[id], st[id^1]);
      }

      int query(int l, int r){
            int mn = inf;
            l += n; r += n+1;
            for(; l < r; l >>= 1, r >>= 1){
                  if(l&1){
                        minimize(mn, st[l++]);
                  }

                  if(r&1){
                        minimize(mn, st[--r]);
                  }
            }
            return mn;
      }
};

void dfs(int i, SegmentTreeMin& minL, SegmentTreeMax& maxR, DSU& dsu){
      //constructing a arbitrary spanning tree
      minL.update(r[i], +inf);
      maxR.update(l[i], -inf);

      while(true){
            int lo = minL.query(l[i]+1, r[i]-1);
            if(lo < l[i]){
                  int j = inv_from_l[lo];
                  color[j] = 3 - color[i];
                  dsu.join(i, j);
                  dfs(j, minL, maxR, dsu);
            } else break;
      }

      while(true){
            int hi = maxR.query(l[i]+1, r[i]-1);
            if(r[i] < hi){
                  int j = inv_from_r[hi];
                  color[j] = 3 - color[i];
                  dsu.join(i, j);
                  dfs(j, minL, maxR, dsu);
            } else break;
      }
}

bool check_color(int c){ //checking whether the graph can be bipartite graph
      vpi events;
      FOR(i, 0, N){
            if(color[i] == c){
                  events.eb(l[i], +(i+1));
                  events.eb(r[i], -(i+1));
            }
      }

      sort(all(events));
      stack<int> online;
      FOR(i, 0, sz(events)){
            int id = events[i].ss;
            if(id > 0) online.push(id);
            else{
                  if(online.top() != -id) return false;
                  online.pop();
            }
      }
      return true;
}

int main(){
      setIO();

      cin >> N;

      SegmentTreeMin minL(2 * N);
      SegmentTreeMax maxR(2 * N);
      FOR(i, 0, N){
            cin >> l[i] >> r[i];
            --l[i], --r[i];
            inv_from_l[l[i]] = i;
            inv_from_r[r[i]] = i;
            minL.update(r[i], l[i]);
            maxR.update(l[i], r[i]);
      }

      DSU dsu(N);
      FOR(i, 0, N){
            if(!color[i]){
                  color[i] = 1;
                  dfs(i, minL, maxR, dsu);
            }
      }

      if(!check_color(1) || !check_color(2)) {
            cout << 0 << '\n';
            return 0;
      }

      int ans = 1;
      FOR(i, 0, dsu.components){
            ans += ans;
            if(ans >= mod) ans -= mod;
      }
      cout << ans << '\n';

      return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void setIO()':
port_facility.cpp:56:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |             freopen("B.inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:57:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |             freopen("B.out", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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