Submission #656122

#	Time	Username	Problem	Language	Result	Execution time	Memory
656122		ParsaS	Port Facility (JOI17_port_facility)	C++17	78 / 100	6048 ms	809916 KiB

port_facility

// In the name of God
#include<bits/stdc++.h>
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];
queue<int> Q;

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) {
    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);
}
void shift(int v, int Tl, int Tr) {
    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();
    }
    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) {
    shift(v, Tl, Tr);
    if (Tl > r || Tr < l)
        return;
    if (Tl >= l && Tr <= r) {
        while (!R[v].empty() && rt[R[v].back()] >= Rt) {
            shift(v, Tl, Tr);
            while (!R[v].empty() && col[R[v].back()] == -1 && rt[R[v].back()] >= Rt) {
                col[R[v].back()] = c;
                Q.push(R[v].back());
                mxr[v][c] = max(mxr[v][c], rt[R[v].back()]);
                R[v].pop_back();
            }
        }
        while (!L[v].empty() && lt[L[v].back()] <= Lt) {
            shift(v, Tl, Tr);
            while (!L[v].empty() && col[L[v].back()] == -1 && lt[L[v].back()] <= Lt) {
                col[L[v].back()] = c;
                Q.push(L[v].back());
                mnl[v][c] = min(mnl[v][c], lt[L[v].back()]);
                L[v].pop_back();
            }
        }
        shift(v, Tl, Tr);
        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);
    shift(v, Tl, 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) {
    shift(v, Tl, Tr);
    if (l > Tr || r < Tl) {
        return mp(2 * n + 1, 0);
    }
    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));
}

bool bfs(int s) {
    col[s] = 1;
    Q.push(s);
    bool ok = true;
    while (!Q.empty()) {
        int v = Q.front();
        Q.pop();
        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:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while (l < A.size() && r < B.size()) {
      |            ~~^~~~~~~~~~
port_facility.cpp:19:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while (l < A.size() && r < B.size()) {
      |                            ~~^~~~~~~~~~
port_facility.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while (l < A.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 (r < B.size())
      |            ~~^~~~~~~~~~

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