Submission #395019

#	Time	Username	Problem	Language	Result	Execution time	Memory
395019		parsabahrami	Port Facility (JOI17_port_facility)	C++17	78 / 100	6053 ms	346676 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 = 2e6 + 10, MOD = 1e9 + 7;
int al[N], ar[N], M[N], n; pii mx[3][N << 2], mn[3][N << 2]; 

void modify(int t, int p, pii 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) modify(t, p, x, lc, l, md);
    else modify(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]);
}

pair<pii, pii> get(int t, 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[t][id], mn[t][id]};
    int md = (l + r) >> 1;
    pair<pii, pii> a = get(t, ql, qr, lc, l, md), b = get(t, ql, qr, rc, md, r);
    return {max(a.F, b.F), min(a.S, b.S)};
}

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

void DFS(int v, int c = 0) {
    M[v] = 1, remove(0, al[v]), remove(0, ar[v]);
    auto y = get(c + 1, al[v], ar[v]);
    if (y.F.F > ar[v] || y.S.F < al[v]) { printf("0\n"); exit(0); }
    modify(c + 1, al[v], {ar[v], v}), modify(c + 1, ar[v], {al[v], v});
    while (1) {
        pair<pii, pii> x = get(0, 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(0, al[i], {ar[i], i}), modify(0, ar[i], {al[i], i});
    for (int i = 1; i < 3; i++) 
        fill(mx[i], mx[i] + N * 4, pii(-MOD, -MOD)), fill(mn[i], mn[i] + N * 4, pii(MOD, MOD));
    int gc = 0;
    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:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
port_facility.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |         scanf("%d%d", &al[i], &ar[i]), modify(0, al[i], {ar[i], i}), modify(0, ar[i], {al[i], i});
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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