Submission #619538

#	Time	Username	Problem	Language	Result	Execution time	Memory
619538		Hanksburger	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	340 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int c[2000005], a[1000005], b[1000005];
stack<int> s, t;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, ans=1;
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i] >> b[i];
        c[a[i]]=c[b[i]]=i;
    }
    for (int i=1; i<=n*2; i++)
    {
        if (a[c[i]]==i)
        {
            bool x=(s.empty() || b[c[i]]<b[s.top()]);
            bool y=(t.empty() || b[c[i]]<b[t.top()]);
            if (x && y)
            {
                s.push(c[i]);
                ans=(ans*2)%mod;
            }
            else if (x)
                s.push(c[i]);
            else if (y)
                t.push(c[i]);
            else
            {
                cout << 0;
                return 0;
            }
        }
        else
        {
            if (s.size() && s.top()==c[i])
                s.pop();
            else
                t.pop();
        }
    }
    cout << ans;
    return 0;
}

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