Submission #45586

#	Time	Username	Problem	Language	Result	Execution time	Memory
45586		eropsergeev	Port Facility (JOI17_port_facility)	C++14	0 / 100	2 ms	248 KiB

port_facility

#ifdef LOCKAL
    #define _GLIBCXX_DEBUG
#endif
#ifndef LOCKAL
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse3,sse4")
#endif
#include <bits/stdc++.h>
//#define TIMUS
//#define FILENAME "journey"
#ifndef TIMUS
    #include <ext/rope>
    #include <ext/pb_ds/assoc_container.hpp>
#endif // TIMUS
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int INF = INT_MAX / 2;
const ll LINF = (ll)2e18 + 666, M = 1e9 + 7;
const ld EPS = 1e-7;

#ifndef M_PI
    const ld M_PI = acos(-1);
#endif // M_PI

using namespace std;

#ifndef TIMUS
    using namespace __gnu_cxx;
    using namespace __gnu_pbds;

    template<class K, class T>
    using ordered_map = tree<K, T, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

    template<class T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

void run();

template<class T1, class T2>
inline bool mini(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

template<class T1, class T2>
inline bool maxi(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}

int main()
{
    #ifndef LOCKAL
        #ifdef FILENAME
            freopen(FILENAME".in", "r", stdin);
            freopen(FILENAME".out", "w", stdout);
        #endif // FILENAME
    #endif
    #ifndef TIMUS
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif // TIMUS
    srand(time(0));
    auto start = clock();
    run();
    #ifdef LOCKAL
        //cout << endl;
        cout << "\ntime = " << (ld)(clock() - start) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}

#define DEBUG
#if defined DEBUG && defined LOCKAL
    #define debugdo(x) x
#else
    #define debugdo(x)
#endif

#define debug(x) debugdo(cout << x << endl)
#define debug2(x) debugdo(cout << x << " ")

// ---SOLUTION--- //

void run()
{
    int n;
    cin >> n;
    vector<int> e(n * 2), ap(n), bp(n);
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a - 1] = i + 1;
        e[b - 1] = -i - 1;
        ap[i] = a - 1;
        bp[i] = b - 1;
    }
    set<int> s;
    vector<bool> c(n);
    ll ans = 1;
    for (int i = 0; i < n * 2; i++)
    {
        if (e[i] > 0)
        {
            int b = bp[e[i] - 1];
            if (s.lower_bound(i) != s.end() && *s.lower_bound(i) < b)
            {
                c[e[i] - 1] = !c[-e[*s.lower_bound(i)] - 1];
            }
            else
            {
                ans *= 2;
                ans %= M;
            }
            s.insert(bp[e[i] - 1]);
        }
    }
    stack<int> a, b;
    for (auto x: e)
    {
        if (x > 0)
        {
            if (c[x - 1])
                a.push(x);
            else
                b.push(x);
        }
        else
        {
            x = -x;
            if (c[x - 1])
            {
                if (a.top() != x)
                {
                    cout << 0;
                    return;
                }
                a.pop();
            }
            else
            {
                if (b.top() != x)
                {
                    cout << 0;
                    return;
                }
                b.pop();
            }
        }
    }
    cout << ans;
}
/*

*/

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:84:10: warning: unused variable 'start' [-Wunused-variable]
     auto start = clock();
          ^~~~~

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