Submission #897589

#	Time	Username	Problem	Language	Result	Execution time	Memory
897589		andrey27_sm	Port Facility (JOI17_port_facility)	C++17	10 / 100	13 ms	2760 KiB

port_facility

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("arch=icelake-server,avx512f,avx512bw,avx512bitalg,bmi,bmi2")

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr ll mod = 1e9 + 7;

ll bin_pow(ll base, ll exp)
{
    ll res = 1;
    while (exp){
        if (exp & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}
int sgt[8000000];
int min_r[8000000];
/*
void update(int v, int tl, int tr, int pos, int val)
{
    if (tl == tr)
        sgt[v] = val;
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v * 2, tl, tm, pos, val);
        else
            update(v * 2 + 1, tm + 1, tr, pos, val);
        sgt[v] = sgt[v * 2] + sgt[v * 2 + 1];
    }
}
int get(int v, int l, int r, int tl, int tr)
{
    if (l > tr or tl > r)
        return 0;
    if (tl <= l && r <= tr)
        return sgt[v];
    int m = (l + r) / 2;
    return get(v * 2, l, m, tl, tr) + get(v * 2 + 1, m + 1, r, tl, tr);
}*/
struct dsu {
    vector<int> p;
    vector<int> sz;
    int szz;
    dsu() {}
    dsu(int n) {
        p.resize(n);
        sz.resize(n);
        for(int i = 0;i < n;i++) {
            p[i] = i;
            sz[i] = 1;
        }
        szz = n;
    }
    int get(int v) {
        if(p[v] == v) {
            return v;
        }
        return p[v] = get(p[v]);
    }
    void unite(int a,int b) {
        a = get(a);
        b = get(b);
        if(a == b) return;
        szz--;
        if(sz[a] < sz[b]) {
            swap(a,b);
        }
        p[b] = a;
        sz[a]+=sz[b];
    }
} D;

void update(int v,int l,int r,int pos, int val) {
    sgt[pos] = val;
}
int get(int v, int l, int r, int tl, int tr) {
    int sum = 0;
    vector<int> to_rem;
    for(int i = tl;i <= tr;i++) {
        sum+=sgt[i];
        if(sgt[i]) {
            to_rem.push_back(i);
            D.unite(tl, i);
        }
        sgt[i] = 0;
    }
    if(to_rem.size()) {
        sgt[to_rem[0]] = 1;
        sgt[to_rem.back()] = 1;
    }
    return sum;
}
int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    ll n;
    cin >> n;
    D = dsu(2*n+1);
    vector<pair<int,int>> events;
    for (int i = 0; i < n; ++i) {
        int l,r;
        cin >> l >> r;
        events.emplace_back(l,r);
        events.emplace_back(r,l);
        D.unite(l,r);
    }
    sort(events.begin(),events.end());
    bool is_pos = true;
    int cnt = n;
    set<int> Rs;
    set<int> Ls;
    for(int i = 0;i < 2*n;i++) {
        if(events[i].first < events[i].second) {
            Ls.insert(events[i].first);
            auto it = Rs.insert(events[i].second);
            if(it.first != Rs.begin()) {
                min_r[events[i].first] = *prev(it.first);
            }
            update(1,1,2*n,events[i].first,1);
        }
        else {
            update(1,1,2*n,events[i].second,0);
            Rs.erase(events[i].first);
            auto it = Ls.find(events[i].second);
            if(it != Ls.end()) {
                it++;
                if(it != Ls.end() and *it < min_r[events[i].second]) {
                    is_pos = false;
                    break;
                }
                it--;
            }
            Ls.erase(it);
            get(1,1,2*n,events[i].second,events[i].first);
        }
    }
    cnt = D.szz-1;
    if(is_pos) {
        cout << bin_pow(2,cnt) << '\n';
    }
    else {
        cout << 0 << '\n';
    }
    return 0;
}

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