Submission #799883

#	Time	Username	Problem	Language	Result	Execution time	Memory
799883		phoenix	Port Facility (JOI17_port_facility)	C++17	100 / 100	2634 ms	141856 KiB

port_facility

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
const int INF = 1e9;
const int M = (1 << 21);

int n;
vector<int>  mn_ver;
vector<int>  mx_ver;
vector<pair<int, int>> segs;

int mn(int x, int y) {
    return (segs[x].first < segs[y].first ? x : y);
}
int mx(int x, int y) {
    return (segs[x].second > segs[y].second ? x : y);
}

void add(int ver) {
    int pos = segs[ver].second;
    for(pos += M, mn_ver[pos] = ver; pos > 1; pos >>= 1) 
        mn_ver[pos >> 1] = mn(mn_ver[pos], mn_ver[pos ^ 1]); 
    pos = segs[ver].first;
    for(pos += M, mx_ver[pos] = ver; pos > 1; pos >>= 1) 
        mx_ver[pos >> 1] = mx(mx_ver[pos], mx_ver[pos ^ 1]); 
}
void del(int ver) {
    int pos = segs[ver].second;
    for(pos += M, mn_ver[pos] = n; pos > 1; pos >>= 1) 
        mn_ver[pos >> 1] = mn(mn_ver[pos], mn_ver[pos ^ 1]); 
    pos = segs[ver].first;
    for(pos += M, mx_ver[pos] = n; pos > 1; pos >>= 1) 
        mx_ver[pos >> 1] = mx(mx_ver[pos], mx_ver[pos ^ 1]); 
}

int get1(int i) {
    int ql = segs[i].first + 1, qr = segs[i].second - 1;
    int res_ver = n;
    for(ql += M, qr += M + 1; ql < qr; ql >>= 1, qr >>= 1) {
        if(ql & 1) {
            res_ver = mn(res_ver, mn_ver[ql++]);
        }
        if(qr & 1) {
            res_ver = mn(res_ver, mn_ver[--qr]);
        }
    }
    return res_ver;
}
int get2(int i) {
    int ql = segs[i].first + 1, qr = segs[i].second - 1;
    int res_ver = n;
    for(ql += M, qr += M + 1; ql < qr; ql >>= 1, qr >>= 1) {
        if(ql & 1) {
            res_ver = mx(res_ver, mx_ver[ql++]);
        }
        if(qr & 1) {
            res_ver = mx(res_ver, mx_ver[--qr]);
        }
    }
    return res_ver;
}

int cl[M];

void dfs(int cur, int color) {
    cl[cur] = color;
    del(cur);
    int next = get1(cur);
    while(segs[next].first < segs[cur].first) {
        dfs(next, 3 - color);
        next = get1(cur);
    }
    
    next = get2(cur);
    while(segs[next].second > segs[cur].second) {
        dfs(next, 3 - color);
        next = get2(cur);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    mn_ver.assign(2 * M, n);
    mx_ver.assign(2 * M, n);
    segs.resize(n + 1);
    segs[n] = {INF, -INF};

    for(int i = 0; i < n; i++) {
        cin >> segs[i].first >> segs[i].second;
        add(i);
    }

    int ans = 1;
    for(int i = 0; i < n; i++) {
        if(cl[i]) continue;
        dfs(i, 1);
        ans = (ans * 2) % MOD;
    }
    vector<int> t[2];
    for(int i = 0; i < n; i++) {
        t[cl[i] - 1].push_back(i);
    }
    sort(t[0].begin(), t[0].end(), [&](int x, int y) {
        if(segs[x].second != segs[y].second) return segs[x].second < segs[y].second;
        return segs[x].first > segs[y].first;
    });
    sort(t[1].begin(), t[1].end(), [&](int x, int y) {
        if(segs[x].second != segs[y].second) return segs[x].second < segs[y].second;
        return segs[x].first > segs[y].first;
    });
    
    for(int c : t[0]) {
        add(c);
        int v = get1(c);
        if(segs[v].first < segs[c].first) {
            cout << 0;
            return 0;
        }
    }
    for(int c : t[0]) del(c);
    for(int c : t[1]) {
        add(c);
        int v = get1(c);
        if(segs[v].first < segs[c].first) {
            cout << 0;
            return 0;
        }
    }
    cout << ans;
}

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