Submission #897845

#	Time	Username	Problem	Language	Result	Execution time	Memory
897845		andrey27_sm	Port Facility (JOI17_port_facility)	C++17	100 / 100	3614 ms	728972 KiB

port_facility

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("arch=icelake-server,avx512f,avx512bw,avx512bitalg,bmi,bmi2")

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr ll mod = 1e9 + 7;


vector<int> sgt1[5000000];
vector<int> sgt2[5000000];
void update1(int v,int l,int r, int pos,int val){
    if(pos > r or pos < l) return;
        sgt1[v].push_back(val);
    if(l == r) {
        return;
    }
    int mid = (l+r)/2;
    update1(v*2,l,mid,pos,val);
    update1(v*2+1,mid+1,r,pos,val);
}
void update2(int v,int l,int r, int pos,int val){
    if(pos > r or pos < l) return;
    sgt2[v].push_back(val);
    if(l == r) {
        return;
    }
    int mid = (l+r)/2;
    update2(v*2,l,mid,pos,val);
    update2(v*2+1,mid+1,r,pos,val);
}
vector<int> tmp;
void get(int v,int l,int r,int tl,int tr) {
    if(tl > r or tr < l) return;
    if(tl <= l and tr >= r) {
        while(!sgt1[v].empty() and sgt1[v].back() < tl) {
            tmp.push_back(sgt1[v].back());
            sgt1[v].pop_back();
        }
        while(!sgt2[v].empty() and sgt2[v].back() > tr) {
            tmp.push_back(sgt2[v].back());
            sgt2[v].pop_back();
        }
        return;
    }
    int m = (l+r)/2;
    get(v*2,l,m,tl,tr);
    get(v*2+1,m+1,r,tl,tr);
}
int O[3000001];
int C[3000001];
pair<int,int> A[3000001];
int B[3000001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int l,r;
        cin >> l >> r;
        A[i] = {l,r};
        B[l] = i;
        B[r] = i;
        O[l] = r;
        O[r] = l;
    }
    for (int i = 2*n; i >= 1;i--) {
        if(O[i] > i)
            update1(1, 1, 2 * n, O[i], i);
    }

    for (int i = 1; i <= 2*n;i++) {
        if(O[i] < i)
            update2(1, 1, 2 * n, O[i], i);
    }
    int cnt = 0;
    for(int i = 0; i < n;i++) {
        if(C[i]) continue;
        cnt++;
        vector<int> c1;
        vector<int> c2;
        queue<pair<int,int>> Q;
        Q.emplace(i,1);
        while(!Q.empty()) {
            auto [v,c] = Q.front();
            Q.pop();
            if(C[v] == c) continue;
            if(C[v] and C[v] != c) {
                cout << 0 << "\n";
                return 0;
            }
            C[v] = c;
            if(c == 1) {
                c1.push_back(v);
            } else {
                c2.push_back(v);
            }
            tmp.clear();
            get(1,1,2*n,A[v].first,A[v].second);
            for(auto e:tmp) {
                Q.emplace(B[e],-c);
            }
        }
        vector<int> starts1;
        for(auto e:c1) starts1.push_back(A[e].first);
        vector<int> starts2;
        for(auto e:c2) starts2.push_back(A[e].first);
        sort(starts1.begin(),starts1.end());
        sort(starts2.begin(),starts2.end());
        stack<int> S;
        for(auto e:starts1) {
            while(!S.empty() and O[S.top()] < e) {
                S.pop();
            }
            if(!S.empty() and O[S.top()] < O[e]) {
                cout << 0 << "\n";
                return 0;
            }
        }
        for(auto e:starts2) {
            while(!S.empty() and O[S.top()] < e) {
                S.pop();
            }
            if(!S.empty() and O[S.top()] < O[e]) {
                cout << 0 << "\n";
                return 0;
            }
        }
    }
    ll ans = 1;
    for (int i = 0; i < cnt;i++) {
        ans *= 2;
        ans %= mod;
    }
    cout << ans << "\n";
    return 0;
}

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