Submission #45616

#	Time	Username	Problem	Language	Result	Execution time	Memory
45616		eropsergeev	Port Facility (JOI17_port_facility)	C++17	100 / 100	5391 ms	774840 KiB

port_facility

#ifdef LOCKAL
    #define _GLIBCXX_DEBUG
#endif
#ifndef LOCKAL
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("unroll-all-loops")
#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_for(x) debug(#x": "); debugdo(for (auto &_x: x)) debug2(_x); debug("")
#define debug(x) debugdo(cout << x << endl)
#define debug2(x) debugdo(cout << x << " ")

// ---SOLUTION--- //

#define FAST 1e9
#ifdef FAST
    char buf[(int)FAST];
    size_t p = 0;
    inline void *operator new(size_t n)
    {
        p += n;
        return buf + p - n;
    }
    inline void operator delete(void *){}
#endif

struct min_f
{
    static int neutral;
    int operator()(int a, int b)
    {
        return min(a, b);
    }
};


struct max_f
{
    static int neutral;
    int operator()(int a, int b)
    {
        return max(a, b);
    }
};

int max_f::neutral;
int min_f::neutral;

template<class T, class F>
struct segtree
{
    F f;
    int n;
    vector<T> a;
    segtree(int n = 0): n(n), a(n * 4, F::neutral){}
    void set(int p, T x, int v = 0, int l = 0, int r = -1)
    {
        if (r == -1)
            r = n;
        if (p < l || p >= r)
            return;
        if (r - l == 1)
        {
            a[v] = x;
            return;
        }
        int c = (r + l) / 2;
        set(p, x, v * 2 + 1, l, c);
        set(p, x, v * 2 + 2, c, r);
        a[v] = f(a[v * 2 + 1], a[v * 2 + 2]);
    }
    T get(int ql, int qr, int v = 0, int l = 0, int r = -1)
    {
        if (r == -1)
            r = n;
        if (ql >= r || l >= qr)
            return F::neutral;
        if (ql <= l && r <= qr)
            return a[v];
        int c = (r + l) / 2;
        return f(get(ql, qr, v * 2 + 1, l, c), get(ql, qr, v * 2 + 2, c, r)); 
    }
};

void run()
{
    max_f::neutral = -INF;
    min_f::neutral = INF;
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    segtree<int, max_f> e(n * 2);
    segtree<int, min_f> s(n * 2);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        e.set(a[i], b[i]);
        s.set(b[i], a[i]);
    }
    vector<int> ev(n * 2);
    for (int i = 0; i < n; i++)
    {
        ev[a[i]] = i + 1;
        ev[b[i]] = -i - 1;
    }
    vector<char> use(n);
    ll ans = 1;
    for (int i = 0; i < n; i++)
    {
        if (!use[i])
        {
            ans = ans * 2 % M;
            queue<int> q;
            q.push(i);
            while (!q.empty())
            {
                int v = q.front();
                q.pop();
                if (!use[v])
                    use[v] = 1;
                debug("v = " << v);
                debug(s.get(6, 7).F);
                e.set(a[v], max_f::neutral);
                s.set(b[v], min_f::neutral);
                while (1)
                {
                    bool f = 0;
                    auto x = e.get(a[v] + 1, b[v]);
                    if (x > b[v])
                    {
                        q.push(-ev[x] - 1);
                        use[-ev[x] - 1] = use[v] ^ 3;
                        debug(v << " - " << x.S);
                        e.set(a[-ev[x] - 1], max_f::neutral);
                        s.set(b[-ev[x] - 1], min_f::neutral);
                        f = 1;
                    }
                    x = s.get(a[v] + 1, b[v]);
                    if (x < a[v])
                    {
                        q.push(ev[x] - 1);
                        use[ev[x] - 1] = use[v] ^ 3;
                        debug(v << " - " << x.S);
                        e.set(a[ev[x] - 1], max_f::neutral);
                        s.set(b[ev[x] - 1], min_f::neutral);
                        f = 1;
                    }
                    if (!f)
                        break;
                }
            }
        }
    }
    #define c use
    for (auto &x: use)
        x--;
    debug_for(use);
    {
        stack<int> a, b;
        for (auto x: ev)
        {
            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;
    }
}
/*
43132142
*/

Compilation message (stderr)

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

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