Submission #658165

#	Time	Username	Problem	Language	Result	Execution time	Memory
658165		ParsaS	Port Facility (JOI17_port_facility)	C++17	78 / 100	6102 ms	949788 KiB

port_facility

// In the name of God
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC optimize("avx2")
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;

const int N = 2e6 + 5, MOD = 1e9 + 7;
int col[N], lt[N], rt[N], mxr[N << 2][2], mnl[N << 2][2];
int n;
pair<int, int> P[N];
vector<int> R[N << 2], L[N << 2];
vector<int> Q;

inline void _merge(vector<int>&A, vector<int>&B, vector<int>&C, int tmp) {
    int l = 0, r = 0;
    while (l < A.size() && r < B.size()) {
        if (tmp ? rt[A[l]] < rt[B[r]] : lt[A[l]] > lt[B[r]]) {
            C.pb(A[l++]);
        }
        else
            C.pb(B[r++]);
    }
    while (l < A.size())
        C.pb(A[l++]);
    while (r < B.size())
        C.pb(B[r++]);
}

void build(int v = 1, int Tl = 1, int Tr = n * 2) {
    L[v].reserve(Tr - Tl + 1);
    R[v].reserve(Tr - Tl + 1);
    for (int c = 0; c < 2; c++) {
        mnl[v][c] = 1e9 + 10;
        mxr[v][c] = -1e9;
    }
    if (Tl == Tr) {
        if (P[Tl].fi) {
            L[v].pb(P[Tl].se);
        }
        else {
            R[v].pb(P[Tl].se);
        }
        return;
    }
    int mid = (Tl + Tr) >> 1;
    int lc = v << 1, rc = v << 1 | 1;
    build(lc, Tl, mid);
    build(rc, mid + 1, Tr);
    _merge(L[lc], L[rc], L[v], 0);
    _merge(R[lc], R[rc], R[v], 1);
}
/*inline void shift(int v, int Tl, int Tr) {
    if (min(mxr[v][0], mxr[v][1]) < 0) {
    while (!R[v].empty() && col[R[v].back()] != -1) {
        mxr[v][col[R[v].back()]] = max(mxr[v][col[R[v].back()]], rt[R[v].back()]);
        R[v].pop_back();
    }
    }
    if (max(mnl[v][0], mnl[v][1]) > 1e9) {
    while (!L[v].empty() && col[L[v].back()] != -1) {
        mnl[v][col[L[v].back()]] = min(mnl[v][col[L[v].back()]], lt[L[v].back()]);
        L[v].pop_back();
    }
    }
}*/
void upd(int l, int r, int Lt, int Rt, int c, int v = 1, int Tl = 1, int Tr = n * 2) {
    if (Tl > r || Tr < l)
        return;
    if (Tl >= l && Tr <= r) {
        while (!R[v].empty() && rt[R[v].back()] >= Rt) {
            if (col[R[v].back()] == -1) {
                col[R[v].back()] = c;
                Q.pb(R[v].back());
                mxr[v][c] = max(mxr[v][c], rt[R[v].back()]);
                R[v].pop_back();
            }
            else {
                mxr[v][col[R[v].back()]] = max(mxr[v][col[R[v].back()]], rt[R[v].back()]);
                R[v].pop_back();
            }
        }
        while (!L[v].empty() && lt[L[v].back()] <= Lt) {
            if (col[L[v].back()] == -1) {
                col[L[v].back()] = c;
                Q.pb(L[v].back());
                mnl[v][c] = min(mnl[v][c], lt[L[v].back()]);
                L[v].pop_back();
            }
            else {
                mnl[v][col[L[v].back()]] = min(mnl[v][col[L[v].back()]], lt[L[v].back()]);
                L[v].pop_back();
            }
        }
        return;
    }
    int mid = (Tl + Tr) >> 1;
    upd(l, r, Lt, Rt, c, v << 1, Tl, mid);
    upd(l, r, Lt, Rt, c, v << 1 | 1, mid + 1, Tr);
    for (int c = 0; c < 2; c++) {
        mnl[v][c] = min(min(mnl[v << 1][c], mnl[v << 1 | 1][c]), mnl[v][c]);
        mxr[v][c] = max(max(mxr[v << 1][c], mxr[v << 1 | 1][c]), mxr[v][c]);
    }
}
pair<int, int> query(int l, int r, int c, int v = 1, int Tl = 1, int Tr = n * 2) {
    if (l > Tr || r < Tl) {
        return mp(2 * n + 1, 0);
    }
    while (mxr[v][c] < 0 && !R[v].empty() && col[R[v].back()] != -1) {
         mxr[v][col[R[v].back()]] = max(mxr[v][col[R[v].back()]], rt[R[v].back()]);
        R[v].pop_back();
    }
    while (mnl[v][c] > 1e9 && !L[v].empty() && col[L[v].back()] != -1) {
        mnl[v][col[L[v].back()]] = min(mnl[v][col[L[v].back()]], lt[L[v].back()]);
        L[v].pop_back();
    }

    if (Tl >= l && Tr <= r) {
        return mp(mnl[v][c], mxr[v][c]);
    }
    int mid = (Tl + Tr) >> 1;
    pair<int, int> pl = query(l, r, c, v << 1, Tl, mid);
    pair<int, int> pr = query(l, r, c, v << 1 | 1, mid + 1, Tr);
    return mp(min(pl.fi, pr.fi), max(pl.se, pr.se));
}

inline bool bfs(int s) {
    col[s] = 1;
    Q.pb(s);
    bool ok = true;
    while (!Q.empty()) {
        int v = Q.back();
        Q.pop_back();
        int L = lt[v], R = rt[v]; 
        pair<int, int> p = query(L + 1, R - 1, col[v]);
        ok &= p.fi >= L && p.se <= R;
        if (!ok) {
            return false;
        }
        upd(L + 1, R - 1, L, R, !col[v]);
    }
    return true;
}

void solve() {
    cin >> n; 
    for (int i = 1; i <= n; i++) {
        int a, b; cin >> a >> b;
        lt[i] = a, rt[i] = b;
        P[a] = mp(0, i);
        P[b] = mp(1, i);
    }
    build();
    memset(col, -1, sizeof col);
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        if (col[i] == -1) {
            ans = 2LL * ans % MOD;
            bool ok = true;
            ok &= bfs(i);
            if (!ok) {
                cout << 0 << '\n';
                return;
            }
        }
    }
    cout << ans << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void _merge(std::vector<int>&, std::vector<int>&, std::vector<int>&, int)':
port_facility.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     while (l < A.size() && r < B.size()) {
      |            ~~^~~~~~~~~~
port_facility.cpp:21:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     while (l < A.size() && r < B.size()) {
      |                            ~~^~~~~~~~~~
port_facility.cpp:28:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while (l < A.size())
      |            ~~^~~~~~~~~~
port_facility.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while (r < B.size())
      |            ~~^~~~~~~~~~

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