Submission #1195668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195668		garam1732	Port Facility (JOI17_port_facility)	C++20	0 / 100	36 ms	86592 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;

int par[MAXN];
int root(int x) {return par[x]==x?x:par[x]=root(par[x]);}
void merge(int x, int y) {
    x = root(x), y = root(y);
    if(x^y) par[x]=y;
}

struct DsuSegTree {
    int tree[MAXN*2*4];
    int lazy[MAXN*2*4];

    void init() {
        memset(tree, -1, sizeof tree);
        memset(lazy, -1, sizeof lazy);
    }

    void prop(int node, int s, int e) {
        if(lazy[node] != -1 && tree[node] != -1) {
            if(s != e) {
                for(auto x : {node<<1, node<<1|1}) {
                    if(lazy[x] != -1) merge(lazy[x], lazy[node]);
                    lazy[x] = lazy[node];
                }
            } else {
                merge(tree[node], lazy[node]);
            }
        } lazy[node] = -1;
    }

    void update(int node, int s, int e, int l, int r, int val) {
        prop(node, s, e);
        if(e < l || r < s) return;
        if(l <= s && e <= r) {
            lazy[node] = val;
            prop(node, s, e);
            return; 
        }

        int mid=s+e>>1;
        update(node<<1, s, mid, l, r, val); update(node<<1|1, mid+1, e, l, r, val);
        tree[node] = max(tree[node<<1], tree[node<<1|1]);
    }

    void set(int node, int s, int e, int idx, int val) {
        prop(node, s, e);
        if(e < idx || idx < s) return;
        if(s == e) {
            tree[node] = val; return;
        }

        int mid=s+e>>1;
        set(node<<1, s, mid, idx, val); set(node<<1|1, mid+1, e, idx, val);
        tree[node] = max(tree[node<<1], tree[node<<1|1]);
    }

    void clean(int node, int s, int e) {
        prop(node, s, e);
        if(s == e) return;

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

struct SegTree {
    int cnt[MAXN*2*4];
    int sum[MAXN*2*4];

    void init(int node, int s, int e) {
        cnt[node] = sum[node] = 0;
        if(s == e) return;

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

    void update(int node, int s, int e, int idx, int val) {
        if(e < idx || idx < s) return;
        if(s == e) {
            cnt[node] = 1;
            sum[node] = val;
            return; 
        }

        int mid=s+e>>1;
        update(node<<1, s, mid, idx, val); update(node<<1|1, mid+1, e, idx, val);
        cnt[node] = cnt[node<<1] + cnt[node<<1|1];
        sum[node] = sum[node<<1] + sum[node<<1|1];
    }

    pi solve(int node, int s, int e, int l, int r) {
        if(e < l || r < s) return pi(0,0);
        if(l <= s && e <= r) return {cnt[node], sum[node]};

        int mid=s+e>>1;
        pi x = solve(node<<1, s, mid, l, r), y = solve(node<<1|1, mid+1, e, l, r);
        return pi(x.ff+y.ff, x.ss+y.ss);
    }
} seg;

struct Inv {
    int l,r,x;
} arr[MAXN];

vector<int> v, w[MAXN];
vector<Inv> tmp;
int main() {
	int n; cin>>n;
    for(int i=0; i<n; i++) {
        cin>>arr[i].l>>arr[i].r; arr[i].x = i;
    } sort(arr, arr+n, [&](Inv &a, Inv &b){return a.l<b.l;});

    for(int i=0; i<n; i++) par[i] = i;

    dsuseg.init();
    for(int i=0; i<n; i++) {
        dsuseg.update(1, 1, n<<1, arr[i].l, arr[i].r, arr[i].x);
        dsuseg.set(1, 1, n<<1, arr[i].r, arr[i].x);
    } dsuseg.clean(1, 1, n<<1); //for(int i=0;i<n;i++)cout<<root(i)<<bl;cout<<endl;

    for(int i=0; i<n; i++) v.push_back(root(i));
    sort(all(v)); comp(v);

    int sz = v.size();
    ll res = 1; for(int i=0; i<sz; i++) res=(res<<1)%MOD;

    sort(arr, arr+n, [&](Inv &a, Inv &b){return a.x<b.x;});
    for(int i=0; i<n; i++) w[lbd(v, root(i))].push_back(i);
    for(int i=0; i<sz; i++) {
        tmp.clear();
        for(int x : w[i]) tmp.push_back(arr[x]);

        v.clear();
        for(auto &x : tmp) {
            v.push_back(x.l); v.push_back(x.r);
        } sort(all(v)); comp(v);
        for(auto &x : tmp) {
            x.l = lbd(v, x.l); x.r = lbd(v, x.r);
        } sort(all(tmp), [&](Inv &a, Inv &b){return a.l<b.l;});

        int m = v.size(); seg.init(1, 0, m-1);
        for(auto &x : tmp) {
            pi t = seg.solve(1, 0, m-1, x.l, x.r);
            if(t.ff == 0) {
                seg.update(1, 0, m-1, x.r, 1);
            } else if(t.ss == t.ff) {
                seg.update(1, 0, m-1, x.r, -1);
            } else if(t.ss == -t.ff) {
                seg.update(1, 0, m-1, x.r, 1);
            } else {
                cout << 0; return 0;
            }
        }
    } cout << res;
}

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