Submission #1259737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259737		Bahamin	Port Facility (JOI17_port_facility)	C++20	100 / 100	2537 ms	298016 KiB

port_facility

#include "bits/stdc++.h"

using namespace std;

template<typename A, typename B> ostream& operator<< (ostream& os, pair<A, B> x) {return os << "(" << x.first << ", " << ")";}
template<typename A> ostream& operator<< (ostream& os, vector<A> x) {string sep; os << "{"; for (A y : x) os << sep << "y", sep = ", "; return os << "}";}

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cin.tie(NULL), cout.tie(NULL), ios_base::sync_with_stdio(false);
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const int MAX_N = 2e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int LOG = 30;

ll inv[MAX_N << 1];
ll fact[MAX_N << 1];
ll fact_inv[MAX_N << 1];

inline int md(ll x) {x %= MOD; return x + (x < 0 ? MOD : 0);}
inline int ADD(ll x, ll y) {return md(x+y);}
inline int SUB(ll x, ll y) {return md(x-y);}
inline int MUL(ll x, ll y) {return md(1ll*x*y);}
inline int POW(ll a, ll b) {int res = 1; while(b){if(b&1)res=MUL(res,a);a=MUL(a,a),b>>=1;}; return res;}
inline int DIV(ll a, ll b) {return MUL(a, POW(b, MOD - 2));}

inline int comb(int n, int k)
{
    if (n < 0 || k < 0 || k < n) return 0;
    return fact[n] * fact_inv[k] % MOD * fact_inv[n - k] % MOD;
}

inline void init()
{
    inv[1] = 1;
    for (int i = 2; i < (MAX_N << 1); i++) inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    fact[0] = 1;
    fact_inv[0] = 1;
    for (int i = 2; i < (MAX_N << 1); i++) fact[i] = fact[i - 1] * i % MOD, fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
}

vector<int> adj[MAX_N];
pair<int, int> a[MAX_N];
int l1[MAX_N];
int r1[MAX_N];
int c[MAX_N];
bool mark[MAX_N];
int n;
pair<pair<int, int>, pair<int, int>> seg[MAX_N << 2];

void build(int l, int r, int id)
{
    if (l == r - 1)
    {
        seg[id] = make_pair(a[l], a[l]);
        return;
    }
    build(l, mid, lid);
    build(mid, r, rid);
    seg[id].first = min(seg[lid].first, seg[rid].first);
    seg[id].second = max(seg[lid].second, seg[rid].second);
}

void upd(int x, int l, int r, int id)
{
    if (l == r - 1)
    {
        seg[id] = make_pair(make_pair(INF, -1), make_pair(-INF, -1));
        return;
    }
    if (x < mid) upd(x, l, mid, lid);
    else upd(x, mid, r, rid);
    seg[id].first = min(seg[lid].first, seg[rid].first);
    seg[id].second = max(seg[lid].second, seg[rid].second);
}

pair<pair<int, int>, pair<int, int>> get(int s, int t, int l, int r, int id)
{
    if (s <= l && t >= r) return seg[id];
    if (s >= r || t <= l) return make_pair(make_pair(INF, -1), make_pair(-INF, -1));
    auto x = get(s, t, l, mid, lid);
    auto y = get(s, t, mid, r, rid);
    return make_pair(min(x.first, y.first), max(x.second, y.second));
}

void dfs(int u, int c1)
{
    mark[u] = true;
    upd(l1[u], 0, n << 1, 1);
    upd(r1[u], 0, n << 1, 1);
    c[u] = c1;
    while (true)
    {
        auto x = get(l1[u], r1[u] + 1, 0, n << 1, 1);
        if (x.first.first < l1[u]) 
        {
            adj[u].push_back(x.first.second);
            adj[x.first.second].push_back(u);
            dfs(x.first.second, 1 - c1);
        } else if (x.second.first > r1[u])
        {
            adj[u].push_back(x.second.second);
            adj[x.second.second].push_back(u);
            dfs(x.second.second, 1 - c1);
        } else break;
    }
}

pair<int, int> fen[MAX_N];

void add(int x, int y)
{
    x++;
    for (int i = x; i < MAX_N; i += i & (-i)) fen[i].first += y, fen[i].second++;
}

pair<int, int> get(int x)
{
    x++;
    pair<int, int> ans;
    for (int i = x; i > 0; i -= i & (-i)) ans.first += fen[i].first, ans.second += fen[i].second;
    return ans;
}

pair<int, int> get(int l, int r)
{
    pair<int, int> ans1 = get(r);
    pair<int, int> ans2 = get(l - 1);
    return make_pair(ans1.first - ans2.first, ans1.second - ans2.second);
}

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> l1[i] >> r1[i];
        l1[i]--;
        r1[i]--;
        a[l1[i]] = {r1[i], i};
        a[r1[i]] = {l1[i], i};
    }
    build(0, n << 1, 1);
    int ans = 1;
    for (int i = 0; i < n; i++) if (!mark[i]) dfs(i, 0), ans = MUL(ans, 2);
    for (int i = n * 2 - 1; i >= 0; i--)
    {
        if (a[i].first > i) continue;
        auto x = get(a[i].first, i);
        if ((x.first > 0 && x.first < x.second) || (x.second && min(x.first, 1) == c[a[i].second])) ans = 0;
        add(a[i].first, c[a[i].second]);
    }
    cout << ans << "\n";    
}

int main()
{
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
}

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