Submission #395047

#	Time	Username	Problem	Language	Result	Execution time	Memory
395047		parsabahrami	Port Facility (JOI17_port_facility)	C++17	100 / 100	5806 ms	264648 KiB

port_facility

/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 2e6 + 5, MOD = 1e9 + 7;
int al[N], ar[N], M[N], n; pii mx[N << 2], mn[N << 2], Q[N / 2]; int MX[2][N << 2], MN[2][N << 2];

void modify(int p, pii x, int id = 1, int l = 1, int r = n * 2 + 1) {
    if (r - l < 2) {
        mx[id] = mn[id] = x;
        return;
    }
    int md = (l + r) >> 1;
    if (p < md) modify(p, x, lc, l, md);
    else modify(p, x, rc, md, r);
    mx[id] = max(mx[lc], mx[rc]);
    mn[id] = min(mn[lc], mn[rc]);
}

pair<pii, pii> get(int ql, int qr, int id = 1, int l = 1, int r = n * 2 + 1) {
    if (qr <= l || r <= ql || ql >= qr) return {{-MOD, -MOD}, {MOD, MOD}};
    if (ql <= l && r <= qr) return {mx[id], mn[id]};
    int md = (l + r) >> 1;
    pair<pii, pii> a = get(ql, qr, lc, l, md), b = get(ql, qr, rc, md, r);
    return {max(a.F, b.F), min(a.S, b.S)};
}

void remove(int p, int id = 1, int l = 1, int r = 2 * n + 1) {
    if (r - l < 2) {
        mx[id] = {-MOD, -MOD}, mn[id] = {MOD, MOD};
        return;
    }
    int md = (l + r) >> 1;
    if (p < md) remove(p, lc, l, md);
    else remove(p, rc, md, r);
    mx[id] = max(mx[lc], mx[rc]);
    mn[id] = min(mn[lc], mn[rc]);
}

void modi(int t, int p, int x, int id = 1, int l = 1, int r = n * 2 + 1) {
    if (r - l < 2) {
        MX[t][id] = MN[t][id] = x;
        return;
    }
    int md = (l + r) >> 1;
    if (p < md) modi(t, p, x, lc, l, md);
    else modi(t, p, x, rc, md, r);
    MX[t][id] = max(MX[t][lc], MX[t][rc]);
    MN[t][id] = min(MN[t][lc], MN[t][rc]);
}

pii geti(int t, int ql, int qr, int id = 1, int l = 1, int r = n * 2 + 1) {
    if (qr <= l || r <= ql) return {-MOD, MOD};
    if (ql <= l && r <= qr) return {MX[t][id], MN[t][id]};
    int md = (l + r) >> 1;
    pii a = geti(t, ql, qr, lc, l, md), b = geti(t, ql, qr, rc, md, r);
    return {max(a.F, b.F), min(a.S, b.S)};
}

void DFS(int v, int c = 0) {
    M[v] = 1, remove(al[v]), remove(ar[v]);
    auto y = geti(c, al[v], ar[v]);
    if (y.F > ar[v] || y.S < al[v]) { printf("0\n"); exit(0); }
    modi(c, al[v], ar[v]), modi(c, ar[v], al[v]);
    while (1) {
        pair<pii, pii> x = get(al[v], ar[v]);
        if (x.F.F > ar[v]) DFS(x.F.S, c ^ 1);
        else if (x.S.F < al[v]) DFS(x.S.S, c ^ 1);
        else break;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d%d", &al[i], &ar[i]), modify(al[i], {ar[i], i}), modify(ar[i], {al[i], i});
    int gc = 0;
    for (int i = 0; i < 2; i++) 
        fill(MX[i], MX[i] + N * 4, -MOD), fill(MN[i], MN[i] + N * 4, MOD);
    for (int i = 1; i <= n; i++) {
        if (!M[i]) DFS(i), gc++;
    }
    int ret = 1;
    for (; gc; gc--) ret = 2ll * ret % MOD;
    printf("%d\n", ret);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
port_facility.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |         scanf("%d%d", &al[i], &ar[i]), modify(al[i], {ar[i], i}), modify(ar[i], {al[i], i});
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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