Submission #873152

#	Time	Username	Problem	Language	Result	Execution time	Memory
873152		tvladm2009	Port Facility (JOI17_port_facility)	C++17	100 / 100	2365 ms	213968 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e6 + 7;
const int M = 1e9 + 7;
const int INF = 2e9;

int add(int a, int b) {
    return a + b >= M ? a + b - M : a + b;
}

int mul(int a, int b) {
    return a * 1ll * b % M;
}

int n;
pair<int, int> a[N];
int ind[N];
int color[N];

struct segtree {
    vector<int> tree;

    segtree() {}

    void init(int n) {
        tree.resize(4 * n + 1);
        build(1, 1, n);
    }

    void build(int v, int tl, int tr) {
        tree[v] = -INF;
        if (tl < tr) {
            int tm = (tl + tr) / 2;
            build(2 * v, tl, tm);
            build(2 * v + 1, tm + 1, tr);
        }
    }

    void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            tree[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update(2 * v, tl, tm, pos, val);
        } else {
            update(2 * v + 1, tm + 1, tr, pos, val);
        }
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
    }

    int query(int v, int tl, int tr, int l, int r, int val) {
        if (tr < l || tl > r) return -1;
        if (l <= tl && tr <= r) {
            if (tree[v] > val) {
                if (tree[v] > 0) {
                    return ind[tree[v]];
                } else {
                    return ind[tree[v] * -1];
                }
            }
            return -1;
        }
        int tm = (tl + tr) / 2;
        int ret = -1;
        ret = query(2 * v, tl, tm, l, r, val);
        if (ret != -1) {
            return ret;
        }
        ret = query(2 * v + 1, tm + 1, tr, l, r, val);
        return ret;
    }

    void delete_kek(int v, int tl, int tr, int pos) {
        if (tl == tr) {
            tree[v] = -INF;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            delete_kek(2 * v, tl, tm, pos);
        } else {
            delete_kek(2 * v + 1, tm + 1, tr, pos);
        }
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
    }
};

segtree kek1, kek2;

void dfs(int v, int c = 0) {
    kek1.delete_kek(1, 1, 2 * n, a[v].first);
    kek2.delete_kek(1, 1, 2 * n, a[v].second);
    color[v] = c;
    while (true) {
        int i = kek1.query(1, 1, 2 * n, a[v].first, a[v].second, a[v].second);
        if (i == -1) {
            break;
        }
        dfs(i, 1 - c);
    }
    while (true) {
        int i = kek2.query(1, 1, 2 * n, a[v].first, a[v].second, -a[v].first);
        if (i == -1) {
            break;
        }
        dfs(i, 1 - c);
    }
}

bool check(vector<pair<int, int>> a) {
    sort(a.begin(), a.end());
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < a.size(); ++i) {
        while (!q.empty() && q.top() < a[i].first) {
            q.pop();
        }
        if (!q.empty() && q.top() < a[i].second) {
            return 0;
        }
        q.push(a[i].second);
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    kek1.init(2 * n);
    kek2.init(2 * n);
    for (int i = 1; i <= n; ++i) {
        kek1.update(1, 1, 2 * n, a[i].first, a[i].second);
        kek2.update(1, 1, 2 * n, a[i].second, -a[i].first);
        ind[a[i].first] = ind[a[i].second] = i;
    }
    for (int i = 1; i <= n; ++i) {
        color[i] = -1;
    }
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (color[i] == -1) {
            ans = mul(ans, 2);
            dfs(i);
        }
    }
    vector<vector<pair<int, int>>> v(2);
    for (int i = 1; i <= n; ++i) {
        v[color[i]].push_back(a[i]);
    }
    if (check(v[0]) && check(v[1])) {
        cout << ans << "\n";
    } else {
        cout << "0\n";
    }
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'bool check(std::vector<std::pair<int, int> >)':
port_facility.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~

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