제출 #1044701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044701		Sharky	Port Facility (JOI17_port_facility)	C++17	100 / 100	2163 ms	382024 KiB

port_facility

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

#define ll long long
const ll mod = 1e9 + 7;

const int N = (1 << 21) + 10;
int p[2 * N], sz[2 * N], pt[2 * N], a[N], b[N], cc = 0;
set<int> disc;
vector<int> seg[2 * N];
ll ans = 1;

int n;

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
}

void update(int pos, int val, int l = 1, int r = 2 * n, int id = 1) {
    seg[id].push_back(val);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (pos <= mid) update(pos, val, l, mid, id * 2);
    else update(pos, val, mid + 1, r, id * 2 + 1);
}

void query(int ql, int qr, int val, int l = 1, int r = 2 * n, int id = 1) {
    if (ql > qr || qr < l || r < ql || seg[id].empty()) return;
    if (ql <= l && r <= qr) {
        merge(val, seg[id][0] + n);
        merge(val + n, seg[id][0]);
        for (int i = pt[id] + 1; i < seg[id].size(); i++) {
            merge(seg[id][i-1], seg[id][i]);
            merge(seg[id][i-1] + n, seg[id][i] + n);
            pt[id]++;
        }
        return;
    }
    int mid = (l + r) / 2;
    query(ql, qr, val, l, mid, id * 2);
    query(ql, qr, val, mid + 1, r, id * 2 + 1);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<int> idx;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        idx.push_back(i);
    }
    iota(p, p + 2 * N, 0);
    fill(sz, sz + 2 * N, 1);
    sort(idx.begin(), idx.end(), [&] (auto x, auto y) {
        return a[x] < a[y];
    });
    for (int i : idx) {
        query(a[i], b[i], i);
        update(b[i], i);
    }
    for (int i = 1; i <= n; i++) {
        if (find(i) == find(i + n)) {
            cout << "0\n";
            return 0;
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        int x = find(i);
        if (x > n) x -= n;
        disc.insert(x);
    }
    int sz = (int) disc.size();
    while (sz--) (ans *= 2LL) %= mod;
    cout << ans << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In function 'void query(int, int, int, int, int, int)':
port_facility.cpp:40:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = pt[id] + 1; i < seg[id].size(); i++) {
      |                                  ~~^~~~~~~~~~~~~~~~

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