Submission #673658

#	Time	Username	Problem	Language	Result	Execution time	Memory
673658		Kahou	Port Facility (JOI17_port_facility)	C++14	100 / 100	2209 ms	109752 KiB

port_facility

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int mod = 1e9 + 7;
int add(int a, int b) {
        a += b;
        if (a >= mod) a -= mod;
        if (a < 0) a += mod;
        return a;
}
int mul(int a, int b) {
        return 1ll*a*b%mod;
}
int pw(int a, int b) {
        int out = 1;
        while (b) {
                if (b&1) out = mul(out, a);
                a = mul(a,a);
                b>>=1;
        }
        return out;
}
const int inf = 1e9 + 50;
const int N = 2e6 + 50;
int n, id[N], c[N];
pii P[N];
pii seg[N<<2][2];
vector<int> A[2];

void build(int u=1, int tl=1, int tr=2*n) {
        if (tl == tr) {
                seg[u][0] = {P[id[tl]].F, id[tl]}, seg[u][1] = {P[id[tl]].S, id[tl]};
                return;
        }
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        build(lc, tl, md), build(rc, md+1, tr);
        seg[u][0] = min(seg[lc][0], seg[rc][0]);
        seg[u][1] = max(seg[lc][1], seg[rc][1]);
}
pii get(int c, int l, int r, int u=1, int tl=1, int tr=2*n) {
        if (r < tl || tr < l) return {(c? -inf:inf), 0};
        if (l <= tl && tr <= r) return seg[u][c];
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        pii A = get(c, l, r, lc, tl, md), B = get(c, l, r, rc, md+1, tr);
        return (c? max(A,B) : min(A,B));
}
void upd(int id, int u=1, int tl=1, int tr=2*n) {
        if (id < tl || tr < id) return;
        if (tl == tr) {
                seg[u][0] = {inf, 0};
                seg[u][1] = {-inf, 0};
                return;
        }
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        upd(id, lc, tl, md), upd(id, rc, md+1, tr);
        seg[u][0] = min(seg[lc][0], seg[rc][0]);
        seg[u][1] = max(seg[lc][1], seg[rc][1]);
}
void pop(int u) {
        upd(P[u].F), upd(P[u].S);
}

void solve() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
                int l, r;
                cin >> l >> r;
                id[l] = id[r] = i;
                P[i] = {l, r};
        }
        for (int u = 1; u <= n; u++) c[u] = -1;
        build();
        queue<int> q;
        int t = 0;
        for (int i = 1; i <= 2*n; i++) {
                if (c[id[i]] >= 0) continue;
                t++;
                c[id[i]] = 0;
                q.push(id[i]);
                pop(id[i]);
                while(q.size()) {
                        int u = q.front();
                        q.pop();
                        pii x = get(0, P[u].S, 2*n);
                        while (x.F < P[u].S) {
                                int v = x.S;
                                c[v] = 1-c[u];
                                q.push(v);
                                pop(v);
                                x = get(0, P[u].S, 2*n);
                        }
                        x = get(1, 1, P[u].F);
                        while (x.F > P[u].F) {
                                int v = x.S;
                                c[v] = 1-c[u];
                                q.push(v);
                                pop(v);
                                x = get(1, 1, P[u].F);
                        }
                }
        }

        bool flg = 1;
        for (int i = 1; i <= 2*n; i++) {
                int u = id[i];
                if (P[u].F == i) A[c[u]].push_back(u);
                else {
                        if (A[c[u]].back() != u) flg = 0;
                        A[c[u]].pop_back();
                }
        }
        cout << (flg? pw(2, t) : 0) << endl;
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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