Submission #1146855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146855		andrei_iorgulescu	Port Facility (JOI17_port_facility)	C++20	100 / 100	4027 ms	154604 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

int modulo = 1e9 + 7;
int inf = 1e9;

int n, a[1000005], b[1000005];

int v1[2000005];///r-ul lui l de aici
int v2[2000005];///l-ul lui r de aici
int dude[2000005];

bool ok(vector<int> inds)
{
    vector<pair<int, int>> w;
    for (auto it : inds)
        w.push_back({a[it], b[it]});
    sort(w.begin(), w.end());
    stack<int> stk;
    for (auto it : w)
    {
        while (!stk.empty() and stk.top() < it.first)
            stk.pop();
        if (!stk.empty() and stk.top() < it.second)
            return false;
        stk.push(it.second);
    }
    return true;
}

pair<int, int> aint1[8000005], aint2[8000005];

void update1(int nod, int l, int r, int pos, pair<int, int> val)
{
    if (l == r)
    {
        aint1[nod] = val;
        return;
    }
    else
    {
        int mij = (l + r) / 2;
        if (pos <= mij)
            update1(2 * nod, l, mij, pos, val);
        else
            update1(2 * nod + 1, mij + 1, r, pos, val);
        aint1[nod] = max(aint1[2 * nod], aint1[2 * nod + 1]);
    }
}

void update2(int nod, int l, int r, int pos, pair<int, int> val)
{
    if (l == r)
    {
        aint2[nod] = val;
        return;
    }
    else
    {
        int mij = (l + r) / 2;
        if (pos <= mij)
            update2(2 * nod, l, mij, pos, val);
        else
            update2(2 * nod + 1, mij + 1, r, pos, val);
        aint2[nod] = min(aint2[2 * nod], aint2[2 * nod + 1]);
    }
}

pair<int, int> query1(int nod, int l, int r, int st, int dr)
{
    if (r < st or dr < l)
        return {-inf, 0};
    else if (st <= l and r <= dr)
        return aint1[nod];
    else
    {
        int mij = (l + r) / 2;
        return max(query1(2 * nod, l, mij, st, dr), query1(2 * nod + 1, mij + 1, r, st, dr));
    }
}

pair<int, int> query2(int nod, int l, int r, int st, int dr)
{
    if (r < st or dr < l)
        return {inf, 0};
    else if (st <= l and r <= dr)
        return aint2[nod];
    else
    {
        int mij = (l + r) / 2;
        return min(query2(2 * nod, l, mij, st, dr), query2(2 * nod + 1, mij + 1, r, st, dr));
    }
}

int find_inters(int x)
{
    if (a[x] + 1 == b[x])
        return -1;
    int l = a[x] + 1, r = b[x] - 1;
    //cout << l << ' ' << r << ' ';
    pair<int, int> p1 = query1(1, 1, 2 * n, l, r), p2 = query2(1, 1, 2 * n, l, r);
    //cout << p1.first << ' ' << p2.first << endl;
    if (p1.first > r)
        return p1.second;
    else if (p2.first < l)
        return p2.second;
    else
        return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= 2 * n; i++)
        v1[i] = -inf, v2[i] = inf;
    for (int i = 1; i <= n; i++)
        v1[a[i]] = b[i], v2[b[i]] = a[i], dude[a[i]] = dude[b[i]] = i;
    for (int i = 1; i <= 2 * n; i++)
        update1(1, 1, 2 * n, i, {v1[i], dude[i]});
    for (int i = 1; i <= 2 * n; i++)
        update2(1, 1, 2 * n, i, {v2[i], dude[i]});
    set<int> s;
    int ans = 1;
    for (int i = 1; i <= n; i++)
        s.insert(i);
    while (!s.empty())
    {
        int x = *s.begin();
        ans = ans * 2 % modulo;
        queue<int> q1, q2;
        vector<int> v1, v2;
        q1.push(x);
        v1.push_back(x);
        update1(1, 1, 2 * n, a[x], {-inf, x});
        update2(1, 1, 2 * n, b[x], {inf, x});
        while (!q1.empty() or !q2.empty())
        {
            if (!q1.empty())
            {
                x = q1.front();
                s.erase(x);
                q1.pop();
                while (true)
                {
                    int y = find_inters(x);
                    //cout << x << ' ' << y << endl;
                    if (y == -1)
                        break;
                    else
                    {
                        q2.push(y);
                        v2.push_back(y);
                        update1(1, 1, 2 * n, a[y], {-inf, y});
                        update2(1, 1, 2 * n, b[y], {inf, y});
                    }
                }
            }
            else
            {
                x = q2.front();
                s.erase(x);
                q2.pop();
                while (true)
                {
                    int y = find_inters(x);
                    //cout << x << ' ' << y << endl;
                    if (y == -1)
                        break;
                    else
                    {
                        //cout << x << ' ' << y << endl;
                        q1.push(y);
                        v1.push_back(y);
                        update1(1, 1, 2 * n, a[y], {-inf, y});
                        update2(1, 1, 2 * n, b[y], {inf, y});
                    }
                }
            }
        }
        if (!ok(v1) or !ok(v2))
        {
            ans = 0;
            break;
        }
    }
    cout << ans;
    return 0;
}

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