Submission #810526

#	Time	Username	Problem	Language	Result	Execution time	Memory
810526		someone	Port Facility (JOI17_port_facility)	C++14	0 / 100	4 ms	8532 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

const int M = 1 << 20, N = 2*M, INF = 1e9 + 42, MOD = 1e9 + 7;

struct Container {
    int deb, fin, id;
};

vector<int> area[2];
vector<Container> ctn;
int n, par[M], deb[M], fin[M], imin[N];

void update(int i, int val) {
    i += M;
    imin[i] = val;
    while(i) {
        i >>= 1;
        if(deb[imin[i*2]] < deb[imin[i*2+1]])
            imin[i] = imin[i*2];
        else
            imin[i] = imin[i*2+1];
    }
}

int getMin(int i, int d, int f, int l, int r) {
    if(f <= l || r <= d)
        return M-1;
    if(l <= d && f <= r)
        return imin[i];
    int mid = (d + f) >> 1,
        ans1 = getMin(i*2, d, mid, l, r),
        ans2 = getMin(i*2+1, mid, f, l, r);
    if(deb[ans1] < deb[ans2])
        return ans1;
    return ans2;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    deb[M-1] = INF;
    for(int i = 0; i < N; i++)
        imin[i] = M-1;
    for(int i = 0; i < n; i++)
        par[i] = i;
    for(int i = 0; i < n; i++) {
        cin >> deb[i] >> fin[i];
        ctn.push_back({deb[i], fin[i], i});
    }
    sort(ctn.begin(), ctn.end(),
    [](Container a, Container b) {
        return a.deb < b.deb;
    });
    area[0].push_back(INF);
    area[1].push_back(INF);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 2; j++)
            while(area[j].back() < ctn[i].deb)
                area[j].pop_back();
        if(area[0].back() < ctn[i].fin && area[1].back() < ctn[i].fin) {
            cout << "0\n";
            return 0;
        }
        if(area[0].back() < ctn[i].fin)
            area[1].push_back(ctn[i].fin);
        else if(area[1].back() < ctn[i].fin)
            area[0].push_back(ctn[i].fin);
        else if(area[0].back() < area[1].back())
            area[0].push_back(ctn[i].fin);
        else
            area[1].push_back(ctn[i].fin);
    }

    sort(ctn.begin(), ctn.end(),
    [](Container a, Container b) {
        return a.fin < b.fin;
    });
    int nb = n;
    for(int i = 0; i < n; i++)
        deb[i] = ctn[i].deb, fin[i] = ctn[i].fin;
    ctn.clear();
    for(int i = 0; i < n; i++)
        ctn.push_back({deb[i], fin[i], i});
    for(int i = 0; i < n; i++) {
        int fi = (int)(lower_bound(fin, fin + n, ctn[i].deb) - fin),
            id = getMin(1, 0, M, fi, i);
        while(deb[id] < ctn[i].deb) {
            deb[ctn[i].id] = min(deb[ctn[i].id], deb[id]);
            nb--;
            update(id, M-1);
            id = getMin(1, 0, M, fi, i);
        }
        update(i, i);
    }
    int ans = 1;
    for(int i = 0; i < nb; i++)
        ans = (ans * 2) % MOD;
    cout << ans << '\n';
}

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