Submission #224390

#TimeUsernameProblemLanguageResultExecution timeMemory
224390osaaateiasavtnlPort Facility (JOI17_port_facility)C++14
100 / 100
1801 ms94512 KiB
#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);
    }   
}   
bool compr(int i, int j) {
    return l[i] < l[j];
}   
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;
        per.app(i);
    }
    sort(all(per), compr);
    build(0, 1, N - 1);
    build_left(0, 1, N - 1);
    int ptr = 0, comp = 1;
    while (1) {
        while (ptr < n && used[per[ptr]])
            ++ptr;
        if (ptr == n)
            break;
        comp = (comp << 1) % MOD;
        q.push(per[ptr]);
        used[per[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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...