Submission #40831

#	Time	Username	Problem	Language	Result	Execution time	Memory
40831		DoanPhuDuc	Port Facility (JOI17_port_facility)	C++98	10 / 100	12 ms	9908 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 LG = 25;
const int INF = 0x3f3f3f3f;
const int BASE = 1e9 + 7;

int n;
int a[N], L[N], R[N], pos[N];

struct DSU {
    int p[N];
    void Init() {
        memset(p, -1, sizeof p);
    }
    int Root(int u) {
        return p[u] < 0 ? u : p[u] = Root(p[u]);
    }
    void Union(int u, int v) {
        u = Root(u); v = Root(v);
        if (u == v) return;
        if (p[u] > p[v]) swap(u, v);
        p[u] += p[v];
        p[v] = u;
    }
} DSU;

set <int> S;

int Find(int v) {
    set <int> :: iterator it = S.lower_bound(v);
    if (it == S.begin()) return -1;
        else return *(--it);
}

struct RMQ {
    int lg[N];
    int spT[2][N][LG];
    void Init() {
        FOR(i, 1, 2 * n) {
            spT[0][i][0] = (a[i] > i ? a[i] : 0);
            spT[1][i][0] = ((a[i] != 0 && a[i] < i) ? a[i] : INF);
        }
        for (int j = 1; 1 << j <= 2 * n; ++j)
            for (int i = 1; i + (1 << j) - 1 <= 2 * n; ++i) {
                spT[0][i][j] = max(spT[0][i][j - 1], spT[0][i + (1 << (j - 1))][j - 1]);
                spT[1][i][j] = min(spT[1][i][j - 1], spT[1][i + (1 << (j - 1))][j - 1]);
            }
        for (int i = 0; 1 << i <= 2 * n; ++i) lg[1 << i] = i;
        FOR(i, 1, 2 * n) if (!lg[i]) lg[i] = lg[i - 1];
    }
    int Query(int t, int l, int r) {
        int k = lg[r - l + 1];
        if (t == 0)return max(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
            else return min(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
    }
} RMQ;

bool Intersect(int x, int y) {
    int l1 = L[x], r1 = R[x];
    int l2 = L[y], r2 = R[y];
    if (l2 > r1 || r2 < l1) return false;
    if (l1 < l2 && r2 < r1) return false;
    if (l2 < l1 && r1 < r2) 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);
        L[i] = l; R[i] = r;
        a[l] = r;
        a[r] = l;
        pos[l] = i;
        pos[r] = i;
    }
    RMQ.Init();
    DSU.Init();
    FOR(timer, 1, 2 * n) {
        if (a[timer] == 0) continue;
        if (a[timer] > timer) {
            int l2 = timer, r2 = a[timer];
            int r1 = Find(r2);
            if (r1 != -1) {
                if (l2 < r1 && RMQ.Query(0, l2, r1) > r2) {
                    puts("0");
                    return 0;
                }
            }
            S.insert(a[timer]);
        } else {
            S.erase(timer);
        }
    }
    int fre = 0;
    FOR(timer, 1, 2 * n) {
        if (a[timer] > timer) {
            int l = timer, r = a[timer];
            int lMin = RMQ.Query(1, l, r), rMax = RMQ.Query(0, l, r);
            if (lMin < l) DSU.Union(pos[timer], pos[lMin]);
            if (rMax > r) DSU.Union(pos[timer], pos[rMax]);
        }
    }
    int cmp = 0;
    FOR(i, 1, n) if (DSU.p[i] < 0) ++cmp;
    int ans = 1;
    FOR(i, 1, cmp) ans = (LL)ans * 2 % BASE;
    cout << ans;
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:113:9: warning: unused variable 'fre' [-Wunused-variable]
     int fre = 0;
         ^
port_facility.cpp:86:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
port_facility.cpp:88: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: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22