Submission #414930

#	Time	Username	Problem	Language	Result	Execution time	Memory
414930		Pro_ktmr	Port Facility (JOI17_port_facility)	C++17	100 / 100	3216 ms	243412 KiB

port_facility

#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
template<class T> bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
constexpr int dy[4]={-1,0,1,0};
constexpr int dx[4]={0,-1,0,1};

struct UnionFind{
private:
    vector<int> par;
    vector<set<int>> fac;
public:
    void init(int N, vector<int> v){
        par.resize(N);
        fac.resize(N);
        for(int i=0; i<N; i++) par[i] = i;
        for(int i=0; i<N; i++) fac[i].insert(v[i]);
    }
    void unite(int a, int b){
        int rootA = root(a);
        int rootB = root(b);
        if(rootA == rootB) return;
        if(fac[rootA].size() < fac[rootB].size()) swap(rootA, rootB);
        par[rootB] = rootA;
        fac[rootA].merge(fac[rootB]);
    }
    int root(int a){
        if(par[a] == a) return a;
        return par[a] = root(par[a]);
    }
    bool same(int a, int b){
        return root(a) == root(b);
    }
    int size(int a){
        return fac[root(a)].size();
    }
    set<int>& fact(int a){
        return fac[root(a)];
    }
};

template<typename T>
struct WeightedUnionFind{
private:
    vector<int> par;
    vector<int> siz;
    vector<T> dif;
public:
    void init(int N){
        par.resize(N);
        siz.resize(N);
        dif.resize(N);
        for(int i=0; i<N; i++){
            par[i] = i;
            siz[i] = 1;
            dif[i] = 0;
        }
    }
    void unite(int a, int b, T d){
        int rootA = root(a);
        int rootB = root(b);
        if(rootA == rootB) return;
        d += weight(a);
        d -= weight(b);
        if(siz[rootA] < siz[rootB]){
            swap(rootA, rootB);
            d *= -1;
        }
        par[rootB] = rootA;
        dif[rootB] = d;
        siz[rootA] += siz[rootB];
    }
    int root(int a){
        if(par[a] == a) return a;
        int r = root(par[a]);
        dif[a] += dif[par[a]];
        return par[a] = r;
    }
    bool same(int a, int b){
        return root(a) == root(b);
    }
    int size(int a){
        return siz[root(a)];
    }
    T weight(int a){
        root(a);
        return dif[a];
    }
    T diff(int a, int b){
        return weight(b) - weight(a);
    }
};

template<typename T>
struct SegmentTree{
private:
    int n, N;
    vector<T> node;
    function<T(T, T)> F;
    T E;
public:
    void init(int _n, function<T(T, T)> f, T e){
        F = f;
        E = e;
        n = _n;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, e);
    }
    void init(vector<T> v, function<T(T, T)> f, T e){
        F = f;
        E = e;
        n = v.size();
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, e);
        for(int i=0; i<n; i++) node[N-1+i] = v[i];
        for(int i=N-2; i>=0; i--) node[i] = F(node[(i<<1)+1], node[(i<<1)+2]);
    }
    T& operator [](int a){
        return node[N-1+a];
    }
    void update(int a, T x){
        a += N-1;
        node[a] = x;
        while(a > 0){
            a = (a-1)>>1;
            node[a] = F(node[(a<<1)+1], node[(a<<1)+2]);
        }
    }
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        if(b <= l || r <= a) return E;
        if(a <= l && r <= b) return node[k];
        return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
    int find_right(function<bool(T)> g, int a){
        if(!g(E)) return -1;
        T t = E;
        return min(find_right(g, a, 0, 0, N, t), n);
    }
    int find_right(function<bool(T)> g, int a, int k, int l, int r, T &t){
        if(r-l == 1){
            t = F(t, node[k]);
            return g(t) ? r : a;
        }
        int m = (l + r) >> 1;
        if(m <= a) return find_right(g, a, (k<<1)+2, m, r, t);
        if(a <= l && g(F(t, node[k]))){
            t = F(t, node[k]);
            return r;
        }
        int L = find_right(g, a, (k<<1)+1, l, m, t);
        if(L < m) return L;
        int R = find_right(g, a, (k<<1)+2, m, r, t);
        return max(L, R);
    }
    int find_left(function<bool(T)> g, int b){
        if(!g(E)) return n + 1;
        T t = E;
        return find_left(g, b, 0, 0, N, t);
    }
    int find_left(function<bool(T)> g, int b, int k, int l, int r, T t){
        if(r-l == 1){
            t = F(node[k], t);
            return g(t) ? l : b;
        }
        int m = (l + r) >> 1;
        if(b <= m) return find_left(g, b, (k<<1)+1, l, m, t);
        if(r <= b && g(F(node[k], t))){
            t = F(node[k], t);
            return l;
        }
        int R = find_left(g, b, (k<<1)+2, m, r, t);
        if(m < R) return R;
        int L = find_left(g, b, (k<<1)+1, l, m, t);
        return min(L, R);
    }
};

struct Monoid{
    int a, b;
    friend Monoid operator*(const Monoid& a, const Monoid& b){
        return {a.a+b.a,a.b+b.b};
    }
};

int N;
vector<int> A, B;
int P[2000000];

SegmentTree<Monoid> segtree;

UnionFind uf;
WeightedUnionFind<int> wuf;

set<int> ls[1000000];

signed main(){
	scanf("%d", &N);
    A.resize(N); B.resize(N);
	rep(i, N){
		scanf("%d%d", &A[i], &B[i]);
		A[i]--; B[i]--;
		P[A[i]] = i-1e9;
		P[B[i]] = i;
	}

    uf.init(N, B);
    wuf.init(N);
	set<int> st;
	rep(i, 2*N){
		if(P[i] < 0){
			if(st.size() && *st.begin() < B[P[i]+1e9]){
				int tmp = *st.begin();
				while(st.size() && *st.begin() < B[P[i]+1e9]){
                    uf.unite(P[*st.begin()], P[i]+1e9);
                    wuf.unite(P[*st.begin()], P[i]+1e9, 1);
					st.erase(st.begin());
				}
                st.insert(tmp);
			}
			else{
				st.insert(B[P[i]+1e9]);
			}
		}
		else{
			st.erase(i);
            auto itr = uf.fact(P[i]).upper_bound(i);
            if(itr != uf.fact(P[i]).end()){
                st.insert(*itr);
            }
		}
	}

    segtree.init(2*N, [](Monoid a, Monoid b){ return a*b; }, {0,0});
    rep(k, N){
        if(uf.root(k) == k){
            vector<int> v;
            for(auto itr=uf.fact(k).begin(); itr!=uf.fact(k).end(); itr++){
                v.pb(*itr);
                v.pb(A[P[*itr]]);
            }
            sort(all(v));
            for(int i: v){
                if(P[i] < 0){
                    Monoid m = segtree.query(i, B[P[i]+1e9]);
                    if((wuf.diff(k, P[i]+1e9)+2*N)%2 == 0){
                        if(m.a > 0){
                            printf("0\n");
                            exit(0);
                        }
                        segtree.update(B[P[i]+1e9], {1,0});
                    }
                    else{
                        if(m.b > 0){
                            printf("0\n");
                            exit(0);
                        }
                        segtree.update(B[P[i]+1e9], {0,1});
                    }
                }
                else{
                    segtree.update(i, {0,0});
                }
            }
        }
    }

    ll ans = 1;
    rep(i, N) (ans *= (uf.root(i) == i ? 2 : 1)) %= MOD;
    printf("%lld\n", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
port_facility.cpp:215:2: note: in expansion of macro 'rep'
  215 |  rep(i, N){
      |  ^~~
port_facility.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
port_facility.cpp:225:2: note: in expansion of macro 'rep'
  225 |  rep(i, 2*N){
      |  ^~~
port_facility.cpp:15:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
port_facility.cpp:250:5: note: in expansion of macro 'rep'
  250 |     rep(k, N){
      |     ^~~
port_facility.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
port_facility.cpp:284:5: note: in expansion of macro 'rep'
  284 |     rep(i, N) (ans *= (uf.root(i) == i ? 2 : 1)) %= MOD;
      |     ^~~
port_facility.cpp:213:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
port_facility.cpp:216:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |   scanf("%d%d", &A[i], &B[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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