제출 #224392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224392		osaaateiasavtnl	Port Facility (JOI17_port_facility)	C++14	100 / 100	1753 ms	77288 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e6 + 7, MOD = 1000 * 1000 * 1000 + 7;
int l[N], r[N], mn[N << 2], mx[N << 2], num[N], numr[N];
bool ans[N], used[N];  
void relax(int v) {
    mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}   
void build(int v, int tl, int tr) {
    if (tl == tr) {
        if (num[tl])    
            mx[v] = r[num[tl]];
        return;
    }   
    int tm = (tl + tr) >> 1;
    build(v * 2 + 1, tl, tm); build(v * 2 + 2, tm + 1, tr);
    relax(v);
}   
void relax_left(int v) {
    mn[v] = min(mn[v * 2 + 1], mn[v * 2 + 2]);
}   
void build_left(int v, int tl, int tr) {
    if (tl == tr) {
        if (numr[tl])
            mn[v] = l[numr[tl]];
        else
            mn[v] = N;
        return;
    }
    int tm = (tl + tr) >> 1;
    build_left(v * 2 + 1, tl, tm); build_left(v * 2 + 2, tm + 1, tr);
    relax_left(v);             
}
queue <int> q;
void color(int v, int tl, int tr, int l, int r, int x, bool c) {
    if (tr < l || r < tl || mx[v] <= x)
        return;
    if (tl == tr) {
        int i = num[tl];
        if (!used[i]) {
            used[i] = 1;
            ans[i] = c;
            q.push(i);
        }
        mx[v] = 0;
        return;
    }   
    int tm = (tl + tr) >> 1;
    color(v * 2 + 1, tl, tm, l, r, x, c);
    color(v * 2 + 2, tm + 1, tr, l, r, x, c);
    relax(v);
}   
void color_left(int v, int tl, int tr, int l, int r, int x, bool c) {
    if (tr < l || r < tl || mn[v] >= x)
        return;
    if (tl == tr) {
        int i = numr[tl];
        if (!used[i]) {
            used[i] = 1;
            ans[i] = c;
            q.push(i);
        }   
        mn[v] = N;
        return;
    }   
    int tm = (tl + tr) >> 1;
    color_left(v * 2 + 1, tl, tm, l, r, x, c);
    color_left(v * 2 + 2, tm + 1, tr, l, r, x, c);
    relax_left(v);
}   
void check(vector <ii> a) {
    sort(all(a));
    vector <int> r = {N};
    for (auto e : a) {
        while (r.back() < e.f)
            r.pop_back();
        if (r.back() < e.s) {
            cout << 0 << endl;
            exit(0);
        }
        r.app(e.s);
    }   
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n;
    cin >> n;
    vector <ii> a;
    vector <int> per;
    for (int i = 1; i <= n; ++i) {
        cin >> l[i] >> r[i];
        num[l[i]] = i;
        numr[r[i]] = i;
    }
    build(0, 1, N - 1);
    build_left(0, 1, N - 1);
    int ptr = 1, comp = 1;
    while (1) {
        while (ptr <= n && used[ptr])
            ++ptr;
        if (ptr == n + 1)
            break;
        comp = (comp << 1) % MOD;
        q.push(ptr);
        used[ptr] = 1;
        while (q.size()) {
            int i = q.front(); q.pop();
            color(0, 1, N - 1, l[i] + 1, r[i] - 1, r[i], ans[i] ^ 1);
            color_left(0, 1, N - 1, l[i] + 1, r[i] - 1, l[i], ans[i] ^ 1);
        }   
    }
    vector <ii> t[2];
    for (int i = 1; i <= n; ++i) 
        t[ans[i]].app(mp(l[i], r[i]));
    for (int i = 0; i < 2; ++i)
        check(t[i]);
    cout << comp << endl;
}

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