Submission #59972349

---

Source Code Expand

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

using ll = long long; 

const int N = 5e5; 

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};
 
struct Tag {
    int set = -1; 
    int act = 0; 
    Tag() {}
    Tag(int s, int a) { set = s; act = a; }
    void apply(Tag t) & {
        if (t.act) {
            act = t.act; 
            set = t.set; 
        } else if (t.set != -1) {
            set = t.set; 
        }
    }
};
 
struct Info {
    int min_x, max_x, active = 0; 
    int y, best = -1; 

    Info() {} 
    Info(int x) {
        min_x = max_x = x;  
    }  
    void apply(Tag t) & {
        if (t.act) {
            active = 1;
            y = t.set; 
            best = y - min_x; 
            assert(min_x == max_x); 
        } else if (t.set != -1 && active) {
            y = t.set; 
            best = y - max_x; 
        }
    }
};
 
Info operator+(const Info &a, const Info &b) {
    Info res; 
    if (a.active && b.active) {
        res.min_x = min(a.min_x, b.min_x); 
        res.max_x = max(a.max_x, b.max_x); 
        res.best = min(a.best, b.best); 
        res.y = min(a.y, b.y); 
        res.active = 1; 
        return res; 
    } else if (a.active) {
        res = a; 
        return a; 
    } else if (b.active) {
        res = b; 
        return res; 
    } else {
        return res; 
    }
}

// [l, r) 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    cin >> n; 
    vector<int> a(n), b(n); 
    for (auto & x: a) cin >> x; 
    for (auto & x: b) cin >> x; 


    set<int> vals; 
    for (int i = 0; i < n; ++i) {
        if (a[i] > b[i]) {
            swap(a[i], b[i]); 
        }
        vals.insert(a[i]); 
        vals.insert(b[i]); 
    }
    map<int, int> to; 
    vector<Info> from; 
    for (auto x: vals) {
        to[x] = from.size(); 
        from.push_back(Info(x)); 
    } 

    LazySegmentTree<Info, Tag> st(from); 
    st.rangeApply(to[a[0]], to[a[0]] + 1, Tag(a[0], 1)); 
    st.rangeApply(to[b[0]], to[b[0]] + 1, Tag(b[0], 1)); 


    // auto print = [&] () {
    //     for (int i = 0; i < from.size(); ++i) {
    //         cout << st.rangeQuery(i, i).best << " \n"[i + 1 == from.size()]; 
    //     }
    // };

    int N = from.size(); 
    for (int i = 0; i < n; ++i) {
        // int ans = 1e9; 
        int f = st.findLast(0, to[a[i]] + 1, [&](const Info x){
            return x.active && x.y < a[i]; 
        }); 
        // cout << "? " << f << '\n'; 
        if (f != -1) {
            st.rangeApply(0, f + 1, Tag(a[i], 0)); 
            // ans = min(ans, st.rangeQuery(0, f + 1).best); 
        }
        auto info = st.rangeQuery(f + 1, to[a[i]] + 1); 
        // if (info.active) ans = min(ans, info.best); 

        if (to[a[i]] < N) {
            info = st.rangeQuery(to[a[i]], N); 
            // cout << "? " << info.active << ' ' << info.y << '\n'; 
            // cout << "AT " << to[a[i]] << ' ' << a[i] << '\n';
            if (info.active) {
                st.rangeApply(to[a[i]], to[a[i]] + 1, Tag(info.y, 1));
                // cout << "D " << st.rangeQuery(to[a[i]], to[a[i]] + 1).best << '\n'; 
                // ans = min(ans, info.best); 
            }
        }

        if (a[i] == b[i]) {
            N = min(N, to[b[i]] + 1); 
            cout << st.rangeQuery(0, N).best << '\n'; 
            continue; 
        }

        int f2 = st.findLast(to[a[i]] + 1, to[b[i]] + 1, [&](const Info x){
            return x.active && x.y < b[i]; 
        }); 
        // cout << "? " << f2 << '\n'; 

        if (f2 != -1) {
            st.rangeApply(to[a[i]] + 1, f2 + 1, Tag(b[i], 0)); 
        }
        
        if (to[b[i]] < N) {
            info = st.rangeQuery(to[b[i]], N); 
            if (info.active) {
                st.rangeApply(to[b[i]], to[b[i]] + 1, Tag(info.y, 1)); 
            }
        }

        N = min(N, to[b[i]] + 1); 
        cout << st.rangeQuery(0, N).best << '\n'; 
    }


    return 0; 
}

Submission Info

Judge Result