Submission #91547

#	Time	Username	Problem	Language	Result	Execution time	Memory
91547		Alexa2001	Port Facility (JOI17_port_facility)	C++17	0 / 100	2 ms	504 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> Pair;
const int Nmax = 2e6 + 5, Mod = 1e9 + 7;

priority_queue < Pair, vector<Pair>, greater<Pair> > heap;

int i, n, x, y;
int where[Nmax], in[Nmax];
vector<Pair> v[5];
int ans = 1;

bool verif(vector<Pair> &v)
{
    while(heap.size()) heap.pop();

    for(auto it : v)
    {
        while(heap.size() && heap.top().first < it.first) heap.pop();

        if(heap.size() && heap.top().first < it.second) return 0;
        heap.push({it.second, -1});
    }
    return 1;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=n; ++i)
    {
        cin >> x >> y;
        in[x] = y;
    }

    for(i=1; i<=2*n; ++i) if(in[i])
    {
        while(heap.size() && heap.top().first < i) heap.pop();

        if(heap.size() && heap.top().first < in[i])
        {
            where[i] = 3 - where[heap.top().second];
            v[where[i]].push_back({i, in[i]});
            heap.push({in[i], i});
            continue;
        }

        where[i] = 1;
        v[1].push_back({i, in[i]});
        heap.push({in[i], i});
        ans = ans * 2 % Mod;
    }

    if(!verif(v[1]) || !verif(v[2])) cout << 0 << '\n';
        else cout << ans << '\n';

    return 0;
}

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