Submission #477533

#	Time	Username	Problem	Language	Result	Execution time	Memory
477533		prvocislo	Port Facility (JOI17_port_facility)	C++17	0 / 100	20 ms	45388 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mod = 1e9 + 7, maxn = 1 << 20;
pair<int, int> st[2][maxn * 2]; // prvy je maximovy, druhy je minimovy
pair<int, int> nic[2] = { {-1, -1}, {maxn + 1, -1} };
void upd(int ly, int i, pair<int, int> p)
{
    st[ly][i += maxn] = p;
    for (i = (i >> 1); i > 0; i >>= 1)
    {
        if (ly == 0) st[ly][i] = max(st[ly][i << 1], st[ly][i << 1 | 1]);
        if (ly == 1) st[ly][i] = min(st[ly][i << 1], st[ly][i << 1 | 1]);
    }
}
pair<int, int> query(int ly, int l, int r)
{
    pair<int, int> ans = nic[ly];
    for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1) ans = ly ? min(ans, st[ly][l++]) : max(ans, st[ly][l++]);
        if (r & 1) ans = ly ? min(ans, st[ly][--r]) : max(ans, st[ly][--r]);
    }
    return ans;
}
vector<int> col(maxn, -1), l(maxn), r(maxn);
int n;
void dfs(int u, int c)
{
    upd(0, l[u], nic[0]);
    upd(1, r[u], nic[1]);
    col[u] = c;
    while (true)
    {
        int v = query(0, 0, l[u] - 1).second;
        if (v == -1 || r[v] < l[u]) break;
        dfs(v, (c ^ 1));
    }
    while (true)
    {
        int v = query(1, r[u] + 1, maxn-1).second;
        if (v == -1 || l[v] > r[u]) break;
        dfs(v, (c ^ 1));
    }
}
bool check(int c)
{
    vector<int> s, ch(2 * n + 1, -1);
    for (int i = 0; i < n; i++) if (col[i] == c)
        ch[l[i]] = i, ch[r[i]] = n + i;
    for (int i = 0; i < 2 * n; i++)
    {
        if (0 <= ch[i] && ch[i] < n) s.push_back(ch[i]);
        else if (ch[i] >= n)
        {
            if (s.back() != ch[i] - n) return false;
            s.pop_back();
        }
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2 * maxn; j++) st[i][j] = nic[i];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> l[i] >> r[i];
        upd(0, l[i], { r[i],i });
        upd(1, r[i], { l[i],i });
    }
    int ans = 1;
    for (int i = 0; i < n; i++) if (col[i] == -1)
    {
        dfs(i, 0);
        ans = (ans << 1) % mod;
    }
    if (check(0) && check(1)) cout << ans << "\n";
    else cout << 0 << "\n";
    return 0;
}

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