Submission #40834

#	Time	Username	Problem	Language	Result	Execution time	Memory
40834		DoanPhuDuc	Port Facility (JOI17_port_facility)	C++98	100 / 100	1309 ms	636032 KiB

port_facility

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

typedef pair <int, int> II;
typedef long long LL;

const int N = 2 * (1e6 + 10);
const int INF = 0x3f3f3f3f;
const int BASE = 1e9 + 7;

int n;
int a[N], b[N], c[N], pos[N];

struct Segment {
    int l, r;
    Segment () {}
    Segment (int l, int r) : l(l), r(r) {}
    bool operator < (const Segment &that) const {
        return l < that.l;
    }
} seg[N];

struct SegmentTree {
    #define m ((l + r) >> 1)
    int st[2][4 * N];
    void Build(int k, int l, int r) {
        if (l == r) {
            st[0][k] = (a[l] > l ? a[l] : 0);
            st[1][k] = (a[l] < l ? a[l] : INF);
            return;
        }
        Build(k << 1, l, m);
        Build(k << 1 | 1, m + 1, r);
        st[0][k] = max(st[0][k << 1], st[0][k << 1 | 1]);
        st[1][k] = min(st[1][k << 1], st[1][k << 1 | 1]);
    }
    void Push1(int k, int l, int r, int i, int j, int val, int u, queue <int> &Q) {
        if (l > j || r < i) return;
        if (st[0][k] < val) return;
        if (l == r) {
            st[0][k] = 0;
            int v = pos[l];
            if (v == u) return;
            if (c[v] == -1) {
                c[v] = c[u] ^ 1;
                Q.push(v);
            }
            return;
        }
        Push1(k << 1, l, m, i, j, val, u, Q);
        Push1(k << 1 | 1, m + 1, r, i, j, val, u, Q);
        st[0][k] = max(st[0][k << 1], st[0][k << 1 | 1]);
    }
    void Push2(int k, int l, int r, int i, int j, int val, int u, queue <int> &Q) {
        if (l > j || r < i) return;
        if (st[1][k] > val) return;
        if (l == r) {
            st[1][k] = INF;
            int v = pos[l];
            if (v == u) return;
            if (c[v] == -1) {
                c[v] = c[u] ^ 1;
                Q.push(v);
            }
            return;
        }
        Push2(k << 1, l, m, i, j, val, u, Q);
        Push2(k << 1 | 1, m + 1, r, i, j, val, u, Q);
        st[1][k] = min(st[1][k << 1], st[1][k << 1 | 1]);
    }
    void Disable(int k, int l, int r, int i) {
        if (l == r) {
            st[0][k] = 0;
            st[1][k] = INF;
            return;
        }
        if (i <= m) Disable(k << 1, l, m, i);
            else Disable(k << 1 | 1, m + 1, r, i);
        st[0][k] = max(st[0][k << 1], st[0][k << 1 | 1]);
        st[1][k] = min(st[1][k << 1], st[1][k << 1 | 1]);
    }
    #undef m
} ST;

bool Check(vector <Segment> &A) {
    sort(A.begin(), A.end());
    memset(b, -1, sizeof b);
    REP(i, 0, A.size()) {
        b[A[i].l] = A[i].r;
        b[A[i].r] = A[i].l;
    }
    stack <int> ST;
    FOR(timer, 1, 2 * n) {
        if (b[timer] == -1) continue;
        if (b[timer] > timer) {
            int l = timer, r = b[timer];
            if (ST.size() == 0 || ST.top() > r) ST.push(r);
                else return false;
        } else {
            int r = timer;
            if (ST.size() && ST.top() == r) ST.pop();
                else return false;
        }
    }
    return true;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d", &n);
    FOR(i, 1, n) {
        int l, r; scanf("%d%d", &l, &r);
        seg[i] = Segment(l, r);
    }
    sort(seg + 1, seg + n + 1);
    memset(c, -1, sizeof c);
    FOR(i, 1, n) {
        int l = seg[i].l, r = seg[i].r;
        pos[l] = i; pos[r] = i;
        a[l] = r; a[r] = l;
    }
    ST.Build(1, 1, 2 * n);
    LL ans = 1;
    FOR(i, 1, n) if (c[i] == -1) {
      //  DEBUG(i);
        queue <int> Q; Q.push(i);
        ST.Disable(1, 1, 2 * n, seg[i].l);
        ST.Disable(1, 1, 2 * n, seg[i].r);
        c[i] = 0;
        while (Q.size()) {
            int u = Q.front(); Q.pop();
            int l = seg[u].l, r = seg[u].r;
            //cout << u << " = " << l << " " << r << endl;
            ST.Push1(1, 1, 2 * n, l, r, r, u, Q);
            ST.Push2(1, 1, 2 * n, l, r, l, u, Q);
        }
        ans = ans * 2 % BASE;
    }
    vector <Segment> Z[2];
    FOR(i, 1, n)  Z[c[i]].push_back(seg[i]);
    FOR(i, 0, 1) if (Check(Z[i]) == false) {
        puts("0");
        return 0;
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'bool Check(std::vector<Segment>&)':
port_facility.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
port_facility.cpp:97:5: note: in expansion of macro 'REP'
     REP(i, 0, A.size()) {
     ^
port_facility.cpp:105:17: warning: unused variable 'l' [-Wunused-variable]
             int l = timer, r = b[timer];
                 ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:122:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
port_facility.cpp:124:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int l, r; scanf("%d%d", &l, &r);
                                        ^

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