Submission #1119379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119379		Neco_arc	Port Facility (JOI17_port_facility)	C++17	100 / 100	2388 ms	210660 KiB

port_facility

#include <bits/stdc++.h>

#define ll long long
#define name "Port Facility"
#define _left id + 1, l, mid
#define _right id + 2 * (mid - l + 1), mid + 1, r
#define fi(i, a, b)  for(int i = a; i <= b; ++i)
#define fid(i, a, b) for(int i = a; i >= b; --i)
#define maxn (int) (1e6 + 1)

const ll mod = 1e9 + 7;

using namespace std;

int n;
pair<int, int> a[maxn];
int cl[maxn];

struct IT {
    int w, sz = 2 * maxn;
    pair<int, int> st[4 * maxn];

    void init(int _w) {
        w = _w;
        fi(i, 1, 4 * maxn - 2) st[i].first = -1e9;
    }

    void update(int id, pair<int, int> val) {
        val.first *= w; st[id += sz] = val;

        while(id != 1) {
            id >>= 1;
            st[id] = max(st[id * 2], st[id * 2 + 1]);
        }
    }

    int get(int l, int r) {
        pair<int, int> ans = {(int) -1e9, 0};

        l += sz, r += sz;
        while(l <= r) {
            ans = max({ans, st[l], st[r]});
            l = (l + 1) >> 1, r = (r - 1) >> 1;
        }

        return ans.second;
    }

} StMax, StMin;

void dfs(int i, int col) {
    cl[i] = col;
    StMin.update(a[i].second, {(int) 1e9, 0});
    StMax.update(a[i].first, {(int) -1e9, 0});

    while(1) {
        int it = StMin.get(a[i].first + 1, a[i].second - 1);
        if(a[it].first > a[i].first || !it) break;

        dfs(it, 3 - col);
    }

    while(1) {
        int it = StMax.get(a[i].first + 1, a[i].second - 1);
        if(a[it].second < a[i].second || !it) break;

        dfs(it, 3 - col);
    }
}

int q[maxn], P[2 * maxn];

bool check(int type) {
    int top = 0;
    fi(i, 1, n) {
        int val = cl[i] == type ? i : -i;
        P[a[i].first] = P[a[i].second] = val;
    }

    fi(i, 1, 2 * n) if(P[i] > 0) {
        if(top && q[top] == P[i]) --top;
        else q[++top] = P[i];
    }

    return !top;
}

void solve() {

    cin >> n;
    fi(i, 1, n) cin >> a[i].first >> a[i].second;

    StMin.init(-1), StMax.init(1);

    fi(i, 1, n) {
        StMin.update(a[i].second, {a[i].first, i});
        StMax.update(a[i].first, {a[i].second, i});
    }

    ll ans = 1;
    fi(i, 1, n) if(!cl[i]) {
        dfs(i, 1);
        ans = ans * 2 % mod;
    }

    if(!check(1) || !check(2)) return cout << 0, void();

    cout << ans << '\n';

}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    solve();

}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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