Submission #1195845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195845		garam1732	Port Facility (JOI17_port_facility)	C++20	100 / 100	2959 ms	420476 KiB

port_facility

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*10;
const ll MOD = 1e9+7;
const ll INF = 2e9;

pi arr[MAXN];
int out[MAXN*2];

int cnt;
int par[MAXN], col[MAXN];
int root(int x) {
    if(par[x] == x) return x;

    int rt = root(par[x]);
    col[x] ^= col[par[x]];
    return par[x] = rt;
}
void merge(int x, int y, int t) {//cout<<x<<bl<<y<<bl<<t<<endl;
    int a = root(x), b = root(y);
    if(a^b) {
        col[a] = col[x]^col[y]^t;
        par[a] = b; cnt--;
    } else if(col[x]^col[y]^t) {
        cnt = -1;
    }
}

struct SegTree {
    vector<int> tree[MAXN*2*4];
    int mx[MAXN*2*4];

    void init(int node, int s, int e) {
        if(s == e) {
            if(out[s]) tree[node].push_back(out[s]);
            return;
        }

        int mid = s+e>>1;
        init(node<<1, s, mid); init(node<<1|1, mid+1, e);
        for(int &x : tree[node<<1]) tree[node].push_back(x);
        for(int &x : tree[node<<1|1]) tree[node].push_back(x);
        sort(all(tree[node]));
    }

    void update(int node, int s, int e, int l, int r, int t) {
        if(e < l || r < s) return;
        if(l <= s && e <= r) {
            if(tree[node].size() && tree[node][0] < t) merge(tree[node][0], t, 1);
            mx[node] = max(mx[node], t);
            return;
        }

        int mid=s+e>>1;
        update(node<<1, s, mid, l, r, t); update(node<<1|1, mid+1, e, l, r, t);
    }

    void construct(int node, int s, int e) {
        for(int i=1; i<tree[node].size() && tree[node][i] < mx[node]; i++) {
            merge(tree[node][i-1], tree[node][i], 0);
        }

        if(s == e) return;

        int mid=s+e>>1;
        construct(node<<1, s, mid), construct(node<<1|1, mid+1, e);
    }
} seg;

int main() {
	int n; cin>>n;
    for(int i=1; i<=n; i++) cin>>arr[i].ff>>arr[i].ss;
    sort(arr+1, arr+n+1); cnt = n;

    for(int i=1; i<=n; i++) out[arr[i].ss] = i, par[i] = i;
    seg.init(1, 1, n<<1);

    for(int i=1; i<=n; i++) {
        seg.update(1, 1, n<<1, arr[i].ff+1, arr[i].ss-1, i);
    } seg.construct(1, 1, n<<1);

    if(cnt < 0) cout << 0;
    else {
        ll res=1;
        while(cnt--) res=(res<<1)%MOD;
        cout<<res;
    }
}

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