Submission #1131669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131669		byunjaewoo	Port Facility (JOI17_port_facility)	C++20	100 / 100	3335 ms	460880 KiB

port_facility

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

const int N=2000010, S=(1<<20), Mod=1e9+7;
int n, ans=1, l[N], r[N], c[N], il[N], ir[N], tl[N], tr[N], tl2[N], tr2[N];
queue<int> q;
vector<int> vl, vr;
class seg {
public:
    seg() {fill(p+1, p+2*S, -1);}
    void upd(int k, int v) {
        for(k+=S-1; k; k>>=1) tree[k].push_back(v), p[k]=tree[k].size()-1;
    }
    void del(int v) {
        chk[abs(v)]=true;
    }
    int query(int l, int r, int v) {
        for(l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
            if(l&1) {
                while(p[l]>=0 && chk[abs(tree[l][p[l]])]) p[l]--;
                if(p[l]>=0 && tree[l][p[l]]>=v) return tree[l][p[l]];
                l++;
            }
            if(!(r&1)) {
                while(p[r]>=0 && chk[abs(tree[r][p[r]])]) p[r]--;
                if(p[r]>=0 && tree[r][p[r]]>=v) return tree[r][p[r]];
                r--;
            }
        }
        if(l==r) {
            while(p[l]>=0 && chk[abs(tree[l][p[l]])]) p[l]--;
            if(p[l]>=0 && tree[l][p[l]]>=v) return tree[l][p[l]];
        }
        return 0;
    }
private:
    vector<int> tree[2*S];
    int p[2*S];
    bool chk[N];
}Tl, Tr;

class seg2 {
public:
    void update(int k, int v) {
        for(k+=S-1; k; k>>=1) tree[k]=max(tree[k], v);
    }
    int query(int l, int r) {
        int ret=0;
        for(l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
            if(l&1) ret=max(ret, tree[l++]);
            if(!(r&1)) ret=max(ret, tree[r--]);
        }
        if(l==r) ret=max(ret, tree[l]);
        return ret;
    }
private:
    int tree[2*S];
}T1, T2;

void dfs(int curr) {
    Tl.del(r[curr]), Tr.del(-l[curr]);
    while(true) {
        int next=ir[Tl.query(tl[curr], tr2[curr], r[curr])];
        if(!next) break;
        c[next]=3-c[curr], dfs(next);
    }
    while(true) {
        int next=il[-Tr.query(tl2[curr], tr[curr], -l[curr])];
        if(!next) break;
        c[next]=3-c[curr], dfs(next);
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    vector<pair<int, int>> tmp1, tmp2;
    for(int i=1; i<=n; i++) {
        cin>>l[i]>>r[i];
        il[l[i]]=i, ir[r[i]]=i;
        vl.push_back(l[i]), vr.push_back(r[i]);
    }
    sort(vl.begin(), vl.end()), sort(vr.begin(), vr.end());
    for(int i=1; i<=n; i++) {
        tl[i]=lower_bound(vl.begin(), vl.end(), l[i])-vl.begin()+1;
        tr[i]=lower_bound(vr.begin(), vr.end(), r[i])-vr.begin()+1;
        tl2[i]=lower_bound(vr.begin(), vr.end(), l[i])-vr.begin()+1;
        tr2[i]=lower_bound(vl.begin(), vl.end(), r[i])-vl.begin();
        tmp1.push_back({r[i], tl[i]}), tmp2.push_back({-l[i], tr[i]});
    }
    sort(tmp1.begin(), tmp1.end()), sort(tmp2.begin(), tmp2.end());
    for(auto [v, k]:tmp1) Tl.upd(k, v);
    for(auto [v, k]:tmp2) Tr.upd(k, v);
    for(int i=1; i<=n; i++) if(!c[i]) {
        c[i]=1, ans=(ans*2)%Mod;
        q.push(i);
        Tl.del(r[i]), Tr.del(-l[i]);
        while(!q.empty()) {
            int curr=q.front(); q.pop();
            while(true) {
                int next=ir[Tl.query(tl[curr], tr2[curr], r[curr])];
                if(!next) break;
                c[next]=3-c[curr], Tl.del(r[next]), Tr.del(-l[next]), q.push(next);
            }
            while(true) {
                int next=il[-Tr.query(tl2[curr], tr[curr], -l[curr])];
                if(!next) break;
                c[next]=3-c[curr], Tl.del(r[next]), Tr.del(-l[next]), q.push(next);
            }
        }
    }
    for(int i=1; i<=n; i++) {
        if(c[i]==1) T1.update(tl[i], r[i]);
        else T2.update(tl[i], r[i]);
    }
    for(int i=1; i<=n; i++) {
        if(c[i]==1) {
            if(T1.query(tl[i], tr2[i])>r[i]) {
                cout<<0; return 0;
            }   
        }
        else {
            if(T2.query(tl[i], tr2[i])>r[i]) {
                cout<<0; return 0;
            }
        }
    }
    cout<<ans;
    return 0;
}

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