Submission #1118053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118053		Hamed_Ghaffari	Port Facility (JOI17_port_facility)	C++17	78 / 100	6107 ms	912260 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 2e6 + 5;
const int LOG = 23;

int n, ptr[MXN<<2];
pii A[MXN];
vector<int> seg[MXN<<2];

void add_seg(int p, int x, int l=1, int r=2*n+1, int id=1) {
    if(r-l==1){
        seg[id].pb(x);
        return;
    }
    if(p<mid) add_seg(p, x, l, mid, lc);
    else add_seg(p, x, mid, r, rc);
}
void build(int l=1, int r=2*n+1, int id=1) {
    if(r-l==1) return;
    build(l, mid, lc);
    build(mid, r, rc);
    int i=0, j=0;
    while(i<SZ(seg[lc]) && j<SZ(seg[rc]))
        seg[id].pb(A[seg[lc][i]].X<A[seg[rc][j]].X ? seg[lc][i++] : seg[rc][j++]);
    while(i<SZ(seg[lc])) seg[id].pb(seg[lc][i++]);
    while(j<SZ(seg[rc])) seg[id].pb(seg[rc][j++]);
}

vector<pii> g[MXN];
void add_edge(int u, int v, int w) {
    g[u].pb(Mp(v,w));
    g[v].pb(Mp(u,w));
}

void add(int s, int e, int i, int l=1, int r=2*n+1, int id=1) {
    if(s<=l && r<=e) {
        if(!seg[id].empty() && A[seg[id][0]].X<A[i].X) add_edge(seg[id][0], i, 3);
        while(ptr[id]+1<SZ(seg[id]) && A[seg[id][ptr[id]+1]].X<A[i].X)
            add_edge(seg[id][0], seg[id][++ptr[id]], 0);
        return;
    }
    if(s<mid) add(s, e, i, l, mid, lc);
    if(e>mid) add(s, e, i, mid, r, rc);
}

int col[MXN];

void dfs(int v, int c) {
    col[v] = c;
    for(auto [u, w] : g[v])
        if(!col[u]) dfs(u, c^w);
        else if(col[u] != (c^w)) {
            cout << "0\n";
            exit(0);
        }
}

void Main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> A[i].X >> A[i].Y;
        add_seg(A[i].Y, i);
    }
    build();
    for(int i=1; i<=n; i++) add(A[i].X, A[i].Y, i);
    int ans=1;
    for(int i=1; i<=n; i++)
        if(!col[i]) {
            dfs(i, 1);
            ans <<= 1;
            if(ans>=MOD) ans -= MOD;
        }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

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