Submission #1105658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105658		vladilius	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	336 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int mod = 1e9 + 7;
const int inf = 1e9;

struct ST{
    vector<int> t, all;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
    }
    void upd(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            t[v] = x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v] = max(t[vv], t[vv + 1]);
    }
    void upd(int p, int x){
        upd(1, 1, n, p, x);
    }
    void find(int v, int tl, int tr, int& l, int& r, int& x){
        if (l > tr || r < tl || t[v] <= x) return;
        if (tl == tr){
            all.pb(tl);
            t[v] = -inf;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        find(vv, tl, tm, l, r, x);
        find(vv + 1, tm + 1, tr, l, r, x);
        t[v] = max(t[vv], t[vv + 1]);
    }
    vector<int> find(int l, int r, int x){
        all.clear();
        find(1, 1, n, l, r, x);
        return all;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1), b(n + 1);
    vector<arr3> all1 = {{}}, all2 = {{}};
    for (int i = 1; i <= n; i++){
        cin>>a[i]>>b[i];
        all1.pb({a[i], b[i], i});
        all2.pb({b[i], a[i], i});
    }
    
    sort(all1.begin(), all1.end());
    sort(all2.begin(), all2.end());
    
    vector<int> x1 = {0}, y1 = {0}, p1(n + 1), p2(n + 1);
    ST T1(n), T2(n);
    for (int i = 1; i <= n; i++){
        T1.upd(i, all1[i][1]); x1.pb(all1[i][0]); p1[all1[i][2]] = i;
        T2.upd(i, -all2[i][1]); y1.pb(all2[i][0]); p2[all2[i][2]] = i;
    }
    
    vector<int> :: iterator it1, it2;
    
    auto rem1 = [&](int i){
        T1.upd(p1[i], -inf);
    };
    auto rem2 = [&](int i){
        T2.upd(p2[i], -inf);
    };
    
    vector<bool> used(n + 1), t(n + 1);
    queue<int> q;
    vector<int> all;
    int out = 1, l, r;
    for (int i = 1; i <= n; i++){
        if (used[i]) continue;
        
        q.push(i);
        used[i] = t[i] = 1;
        rem1(i); rem2(i);
        
        while (!q.empty()){
            int j = q.front(); q.pop();
            
            it1 = upper_bound(x1.begin(), x1.end(), a[j]);
            it2 = lower_bound(x1.begin(), x1.end(), b[j]);
            l = (int) (it1 - x1.begin()); r = (int) (it2 - x1.begin()) - 1;
            if (l <= r){
                all = T1.find(l, r, b[j]);
                for (int k: all){
                    k = all1[k][2];
                    used[k] = 1;
                    t[k] = !t[j];
                    q.push(k);
                    rem2(k);
                }
            }
            
            it1 = upper_bound(y1.begin(), y1.end(), a[j]);
            it2 = lower_bound(y1.begin(), y1.end(), b[j]);
            l = (int) (it1 - y1.begin()); r = (int) (it2 - y1.begin()) - 1;
            if (l <= r){
                all = T2.find(l, r, -a[j]);
                for (int k: all){
                    k = all2[k][2];
                    used[k] = 1;
                    t[k] = !t[j];
                    q.push(k);
                    rem1(k);
                }
            }
        }
        
        out = (out * 2) % mod;
    }
    
    vector<pii> st[2 * n + 2];
    for (int i = 1; i <= n; i++){
        st[a[i]].pb({i, 1});
        st[b[i] + 1].pb({i, 0});
    }
    
    vector<int> s[2];
    for (int i = 1; i <= 2 * n; i++){
        for (auto [j, b]: st[i]){
            if (b){
                s[t[j]].pb(j);
            }
            else {
                if (s[t[j]].back() != j){
                    out = 0;
                    break;
                }
                s[t[j]].pop_back();
            }
        }
    }
    
    cout<<out<<"\n";
}

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