Submission #44415

#	Time	Username	Problem	Language	Result	Execution time	Memory
44415		choikiwon	Port Facility (JOI17_port_facility)	C++17	100 / 100	4129 ms	784892 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int mod = 1e9 + 7;
const int MN = 1000010;

int N, M;
pii P[MN], arr[MN << 1];
vector<int> A, B;

struct BIT {
    vector<pii> tree;
    void init() {
        tree = vector<pii>(4 * M);
        build(0, M - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = arr[l];
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    void upd(int idx, pii val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = val;
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    pii quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return pii(-1e9, -1e9);
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        pii L = quer(a, b, l, m, 2*n);
        pii R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit1, bit2;

int col[MN];

void dfs(int u, int c) {
    col[u] = c;

    int l = P[u].first;
    int r = P[u].second;
    bit1.upd(l, {-1e9, -1e9}, 0, M - 1, 1);
    bit2.upd(r, {-1e9, -1e9}, 0, M - 1, 1);

    while(1) {
        pii t = bit1.quer(l, r, 0, M - 1, 1);
        if(t.first < r) break;
        dfs(t.second, c ^ 1);
    }
    while(1) {
        pii t = bit2.quer(l, r, 0, M - 1, 1);
        if(-t.first > l) break;
        dfs(t.second, c ^ 1);
    }
}

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &P[i].first, &P[i].second);
        P[i].first--;
        P[i].second--;
    }

    sort(P, P + N);

    M = N << 1;
    for(int i = 0; i < M; i++) arr[i] = {-1e9, -1e9};
    for(int i = 0; i < N; i++) {
        arr[ P[i].first ] = { P[i].second, i };
    }
    bit1.init();

    for(int i = 0; i < M; i++) arr[i] = {-1e9, -1e9};
    for(int i = 0; i < N; i++) {
        arr[ P[i].second ] = { -P[i].first, i };
    }
    bit2.init();

    memset(col, -1, sizeof(col));
    int cnt = 0;
    for(int i = 0; i < N; i++) if(col[i] == -1) {
        dfs(i, 0);
        cnt++;
    }

    for(int i = 0; i < N; i++) {
        while(A.size() && A.back() < P[i].first) A.pop_back();
        while(B.size() && B.back() < P[i].first) B.pop_back();
        if(col[i]) {
            if(A.size() && A.back() < P[i].second) {
                printf("0");
                return 0;
            }
            A.push_back(P[i].second);
        }
        else {
            if(B.size() && B.back() < P[i].second) {
                printf("0");
                return 0;
            }
            B.push_back(P[i].second);
        }
    }

    int ans = 1;
    for(int i = 0; i < cnt; i++) {
        ans *= 2;
        ans %= mod;
    }
    printf("%d", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
port_facility.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &P[i].first, &P[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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