제출 #659695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659695		ParsaS	Port Facility (JOI17_port_facility)	C++17	78 / 100	6138 ms	968164 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 inxL[N << 2], inxR[N << 2];
int n;
pair<int, int> P[N];
vector<int> R[N << 2], L[N << 2];
int Q[N], inxq;

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;
    }
    inxL[v] = inxR[v] = -1;
    if (Tl == Tr) {
        if (P[Tl].fi) {
            L[v].pb(P[Tl].se);
            inxL[v] = 0;
        }
        else {
            R[v].pb(P[Tl].se);
            inxR[v] = 0;
        }
        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);
    inxL[v] = L[v].size() - 1;
    inxR[v] = R[v].size() - 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 (inxR[v] >= 0 && rt[R[v][inxR[v]]] >= Rt) {
            if (col[R[v][inxR[v]]] == -1) {
                col[R[v][inxR[v]]] = c;
                Q[inxq++] = R[v][inxR[v]];
                mxr[v][c] = max(mxr[v][c], rt[R[v][inxR[v]]]);
                inxR[v]--;
            }
            else {
                mxr[v][col[R[v][inxR[v]]]] = max(mxr[v][col[R[v][inxR[v]]]], rt[R[v][inxR[v]]]);
                inxR[v]--;
            }
        }
        while (inxL[v] >= 0 && lt[L[v][inxL[v]]] <= Lt) {
            if (col[L[v][inxL[v]]] == -1) {
                col[L[v][inxL[v]]] = c;
                Q[inxq++] = L[v][inxL[v]];
                mnl[v][c] = min(mnl[v][c], lt[L[v][inxL[v]]]);
                inxL[v]--;
            }
            else {
                mnl[v][col[L[v][inxL[v]]]] = min(mnl[v][col[L[v][inxL[v]]]], lt[L[v][inxL[v]]]);
                inxL[v]--;
            }
        }
        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 && inxR[v] >= 0 && col[R[v][inxR[v]]] != -1) {
         mxr[v][col[R[v][inxR[v]]]] = max(mxr[v][col[R[v][inxR[v]]]], rt[R[v][inxR[v]]]);
         //mxr[v][col[R[v].back()]] = max(mxr[v][col[R[v].back()]], rt[R[v].back()]);
         inxR[v]--;
    }
    while (mnl[v][c] > 1e9 && inxL[v] >= 0 && col[L[v][inxL[v]]] != -1) {
        mnl[v][col[L[v][inxL[v]]]] = min(mnl[v][col[L[v][inxL[v]]]], lt[L[v][inxL[v]]]);
        //mnl[v][col[L[v].back()]] = min(mnl[v][col[L[v].back()]], lt[L[v].back()]);
        inxL[v]--;
    }

    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;
    inxq = 0;
    Q[inxq++] = s;
    bool ok = true;
    while (inxq) {
        int v = Q[--inxq];
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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