Submission #395005

#	Time	Username	Problem	Language	Result	Execution time	Memory
395005		parsabahrami	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	332 KiB

port_facility

/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
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 = 1e6 + 10, MOD = 1e9 + 7;
int al[N], ar[N], M[N], n; pii mx[N << 2], mn[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]);
}

int edge(int u, int v) {
    if (al[u] > al[v]) swap(u, v);
    return al[u] < al[v] && ar[u] < ar[v] && ar[u] > al[v];
}

void DFS(int v, int p) {
    M[v] = 1, remove(al[v]), remove(ar[v]);
    while (1) {
        pair<pii, pii> x = get(al[v], ar[v]);
        if (x.F.F > ar[v]) { 
            if (~p && edge(p, x.F.S)) { printf("0\n"); exit(0); }
            DFS(x.F.S, v);
        }
        else if (x.S.F < al[v]) { 
            if (~p && edge(p, x.S.S)) { printf("0\n"); exit(0); }
            DFS(x.S.S, v);
        }
        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 = 1; i <= n; i++) {
        if (!M[i]) DFS(i, -1), 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:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
port_facility.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         scanf("%d%d", &al[i], &ar[i]), modify(al[i], {ar[i], i}), modify(ar[i], {al[i], i});
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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