#981461 (C++17) No.2861 Slime Party

提出ソース

結果

問題	No.2861 Slime Party
ユーザー	dyktr_06
提出日時	2024-05-14 04:13:55
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	724 ms / 4,000 ms
コード長	13,415 bytes
コンパイル時間	3,380 ms
コンパイル使用メモリ	235,104 KB
実行使用メモリ	57,440 KB
最終ジャッジ日時	2024-08-25 17:31:49
合計ジャッジ時間	44,600 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	254 ms 57,332 KB
testcase_01	AC	3 ms 6,944 KB
testcase_02	AC	3 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	4 ms 6,940 KB
testcase_12	AC	3 ms 6,940 KB
testcase_13	AC	5 ms 6,940 KB
testcase_14	AC	5 ms 6,940 KB
testcase_15	AC	4 ms 6,940 KB
testcase_16	AC	3 ms 6,940 KB
testcase_17	AC	3 ms 6,944 KB
testcase_18	AC	4 ms 6,940 KB
testcase_19	AC	3 ms 6,940 KB
testcase_20	AC	3 ms 6,944 KB
testcase_21	AC	706 ms 43,344 KB
testcase_22	AC	643 ms 43,412 KB
testcase_23	AC	696 ms 43,580 KB
testcase_24	AC	607 ms 43,508 KB
testcase_25	AC	708 ms 43,392 KB
testcase_26	AC	522 ms 43,460 KB
testcase_27	AC	502 ms 43,404 KB
testcase_28	AC	507 ms 43,436 KB
testcase_29	AC	481 ms 43,376 KB
testcase_30	AC	505 ms 43,620 KB
testcase_31	AC	685 ms 43,360 KB
testcase_32	AC	646 ms 43,368 KB
testcase_33	AC	654 ms 43,404 KB
testcase_34	AC	664 ms 43,432 KB
testcase_35	AC	668 ms 43,380 KB
testcase_36	AC	615 ms 43,384 KB
testcase_37	AC	641 ms 43,452 KB
testcase_38	AC	619 ms 43,332 KB
testcase_39	AC	603 ms 43,400 KB
testcase_40	AC	639 ms 43,448 KB
testcase_41	AC	679 ms 43,404 KB
testcase_42	AC	713 ms 43,476 KB
testcase_43	AC	692 ms 43,424 KB
testcase_44	AC	724 ms 43,480 KB
testcase_45	AC	711 ms 43,376 KB
testcase_46	AC	614 ms 43,480 KB
testcase_47	AC	616 ms 43,404 KB
testcase_48	AC	624 ms 43,388 KB
testcase_49	AC	603 ms 43,372 KB
testcase_50	AC	607 ms 43,424 KB
testcase_51	AC	342 ms 57,264 KB
testcase_52	AC	313 ms 57,376 KB
testcase_53	AC	323 ms 57,384 KB
testcase_54	AC	329 ms 57,216 KB
testcase_55	AC	324 ms 57,440 KB
testcase_56	AC	337 ms 57,216 KB
testcase_57	AC	341 ms 57,308 KB
testcase_58	AC	342 ms 57,312 KB
testcase_59	AC	329 ms 57,292 KB
testcase_60	AC	359 ms 57,264 KB
testcase_61	AC	407 ms 57,428 KB
testcase_62	AC	443 ms 57,272 KB
testcase_63	AC	401 ms 57,180 KB
testcase_64	AC	506 ms 57,380 KB
testcase_65	AC	432 ms 57,272 KB
testcase_66	AC	427 ms 57,280 KB
testcase_67	AC	287 ms 57,288 KB
testcase_68	AC	411 ms 57,196 KB
testcase_69	AC	417 ms 57,256 KB
testcase_70	AC	351 ms 57,300 KB
testcase_71	AC	434 ms 57,280 KB
testcase_72	AC	406 ms 57,320 KB
testcase_73	AC	466 ms 57,280 KB
testcase_74	AC	386 ms 57,276 KB
testcase_75	AC	417 ms 57,300 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

template <typename T>
pair<vector<vector<int>>, int> cartesianTree(vector<T> &a){
    int n = a.size();
    vector<vector<int>> G(n);
    vector<int> par(n, -1), st;
    for(int i = 0; i < n; ++i){
        int prev = -1;
        while(!st.empty() && a[i] > a[st.back()]){
            prev = st.back();
            st.pop_back();
        }
        if(prev != -1){
            par[prev] = i;
        }
        if(!st.empty()){
            par[i] = st.back();
        }
        st.emplace_back(i);
    }
    int root = -1;
    for(int i = 0; i < n; ++i){
        if(par[i] != -1){
            G[par[i]].emplace_back(i);
        } else{
            root = i;
        }
    }
    return make_pair(G, root);
}

class HeavyLightDecomposition{
protected:
    int V;
    vector<vector<int>> G;
    vector<int> stsize, parent, pathtop, depth, in, reverse_in, out;
    int root;

private:
    // Subtree Size
    void buildStsize(int curr, int prev){
        stsize[curr] = 1, parent[curr] = prev;
        for(int &v : G[curr]){
            if(v == prev){
                if(v == G[curr].back()) break;
                else swap(v, G[curr].back());
            }
            buildStsize(v, curr);
            stsize[curr] += stsize[v];
            if(stsize[v] > stsize[G[curr][0]]){
                swap(v, G[curr][0]);
            }
        }
    }

    void buildPath(int curr, int prev, int &t){
        in[curr] = t++;
        reverse_in[in[curr]] = curr;
        for(int v : G[curr]){
            if(v == prev) continue;

            if(v == G[curr][0]){
                pathtop[v] = pathtop[curr];
            } else{
                pathtop[v] = v;
            }
            depth[v] = depth[curr] + 1;
            buildPath(v, curr, t);
        }
        out[curr] = t;
    }

public:
    HeavyLightDecomposition(int node_size) : V(node_size), G(V), stsize(V, 0), parent(V, -1),
        pathtop(V, -1), depth(V, 0), in(V, -1), reverse_in(V, -1), out(V, -1){}

    void add_edge(int u, int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }

    void build(int _root = 0){
        root = _root;
        int t = 0;
        buildStsize(root, -1);
        pathtop[root] = root;
        buildPath(root, -1, t);
    }

    inline int get(int a){
        return in[a];
    }

    int la(int a, int k) {
        while(true){
            int u = pathtop[a];
            if(in[a] - k >= in[u]) return reverse_in[in[a] - k];
            k -= in[a] - in[u] + 1;
            a = parent[u];
        }
    }

    int lca(int a, int b){
        int pa = pathtop[a], pb = pathtop[b];
        while(pathtop[a] != pathtop[b]){
            if(in[pa] > in[pb]){
                a = parent[pa], pa = pathtop[a];
            } else{
                b = parent[pb], pb = pathtop[b];
            }
        }
        if(in[a] > in[b]) swap(a, b);
        return a;
    }

    int dist(int a, int b){ return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }

    int jump(int from, int to, int k) {
        if(!k) return from;
        int l = lca(from, to);
        int d = dist(from, to);
        if(d < k) return -1;
        if(depth[from] - depth[l] >= k) return la(from, k);
        k -= depth[from] - depth[l];
        return la(to, depth[to] - depth[l] - k);
    }

    void subtree_query(int a, const function<void(int, int)> &func){
        func(in[a], out[a]);
    }

    void path_query(int a, int b, const function<void(int, int)> &func, bool include_root = true, bool reverse_path = false){
        vector<pair<int, int>> path;
        int pa = pathtop[a], pb = pathtop[b];
        while(pathtop[a] != pathtop[b]){
            if(in[pa] > in[pb]){
                path.emplace_back(in[pa], in[a] + 1);
                a = parent[pa], pa = pathtop[a];
            } else{
                path.emplace_back(in[pb], in[b] + 1);
                b = parent[pb], pb = pathtop[b];
            }
        }
        if(in[a] > in[b]) swap(a, b);

        if(include_root) path.emplace_back(in[a], in[b] + 1);
        else path.emplace_back(in[a] + 1, in[b] + 1);

        if(!reverse_path) reverse(path.begin(), path.end());
        else for(auto &p : path) p = make_pair(V - p.second, V - p.first);

        for(auto [u, v] : path){
            func(u, v);
        }
    }

    void path_noncommutative_query(int a, int b, const function<void(int, int)> &func, const function<void(int, int)> &func2){
        int l = lca(a, b);
        path_query(a, l, func2, false, true);
        path_query(l, b, func, true, false);
    }
};

template <typename X>
struct SegTree{
    using FX = function<X(X, X)>; // X•X -> X となる関数の型
    int n;
    FX fx;
    const X ex;
    vector<X> dat;

    SegTree(int n_, const FX &fx_, const X &ex_) : n(), fx(fx_), ex(ex_){
        int x = 1;
        while(n_ > x){
            x *= 2;
        }
        n = x;
        dat.assign(n * 2, ex);
    }

    X get(int i) const {
        return dat[i + n];
    }

    void set(int i, const X &x){ dat[i + n] = x; }

    void build(){
        for(int k = n - 1; k >= 1; k--) dat[k] = fx(dat[k * 2], dat[k * 2 + 1]);
    }

    void update(int i, const X &x){
        i += n;
        dat[i] = x;
        while(i > 0){
            i >>= 1;  // parent
            dat[i] = fx(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    X query(int a, int b){
        X vl = ex;
        X vr = ex;
        int l = a + n;
        int r = b + n;
        while(l < r){
            if(l & 1) vl = fx(vl, dat[l++]);
            if(r & 1) vr = fx(dat[--r], vr);
            l >>= 1;
            r >>= 1;
        }
        return fx(vl, vr);
    }

    X operator [](int i) const {
        return dat[i + n];
    }
};

template <class S,
    S(*op)(S, S),
    S(*e)(),
    class F,
    S(*mapping)(F, S),
    F(*composition)(F, F),
    F(*id)()>
struct LazySegTree{
private:
    int _n, size, log;
    vector<S> d;
    vector<F> lz;

    void pull(int k){ d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f){
        d[k] = mapping(f, d[k]);
        if(k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k){
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }

public:
    LazySegTree() : LazySegTree(0){}
    LazySegTree(int n) : LazySegTree(vector<S>(n, e())){}
    LazySegTree(const vector<S> &v) : _n(int(v.size())){
        log = 0;
        size = 1;
        while(size < _n) size <<= 1, log++;
        d = vector<S>(2 * size, e());
        lz = vector<F>(size, id());
        for(int i = 0; i < _n; i++) d[size + i] = v[i];
        for(int i = size - 1; i >= 1; i--){
            pull(i);
        }
    }

    void update(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        for(int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for(int i = 1; i <= log; i++) pull(p >> i);
    }

    S get(int p){
        assert(0 <= p && p < _n);
        p += size;
        for(int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S query(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        if(l == r) return e();

        l += size;
        r += size;

        for(int i = log; i >= 1; i--){
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while(l < r){
            if(l & 1) sml = op(sml, d[l++]);
            if(r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_query(){ return d[1]; }

    void apply(int p, F f){
        assert(0 <= p && p < _n);
        p += size;
        for(int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for(int i = 1; i <= log; i++) pull(p >> i);
    }
    void apply(int l, int r, F f){
        assert(0 <= l && l <= r && r <= _n);
        if(l == r) return;

        l += size;
        r += size;

        for(int i = log; i >= 1; i--){
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while(l < r){
                if(l & 1) all_apply(l++, f);
                if(r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for(int i = 1; i <= log; i++){
            if(((l >> i) << i) != l) pull(l >> i);
            if(((r >> i) << i) != r) pull((r - 1) >> i);
        }
    }

    template <bool (*g)(S)>
    int max_right(int l){
        return max_right(l, [](S x){ return g(x); });
    }
    template <class G>
    int max_right(int l, G g){
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if(l == _n) return _n;
        l += size;
        for(int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do{
            while(l % 2 == 0) l >>= 1;
            if(!g(op(sm, d[l]))){
                while(l < size){
                    push(l);
                    l = (2 * l);
                    if(g(op(sm, d[l]))){
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)>
    int min_left(int r){
        return min_left(r, [](S x){ return g(x); });
    }
    template <class G>
    int min_left(int r, G g){
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if(r == 0) return 0;
        r += size;
        for(int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do{
            r--;
            while(r > 1 && (r % 2)) r >>= 1;
            if(!g(op(d[r], sm))){
                while(r < size){
                    push(r);
                    r = (2 * r + 1);
                    if(g(op(d[r], sm))){
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while((r & -r) != r);
        return 0;
    }
};

const long long INF = 1LL << 60;

using S = long long;
using F = long long;

S op(S l, S r){
    return min(l, r);
}

S e(){
    return INF;
}

S mapping(F f, S x){
    return x + f;
}

F composition(F f, F g){
    return f + g;
}

F id(){
    return 0LL;
}

bool f(S x){
    return x > 0;
}

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

    int n, q;
    long long L;
    cin >> n >> q >> L;
    vector<long long> a(n), x(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }

    auto [G, root] = cartesianTree(a);
    HeavyLightDecomposition hld(n);
    for(int i = 0; i < n; i++){
        for(int j : G[i]){
            hld.add_edge(i, j);
        }
    }
    hld.build(root);

    SegTree<long long> segx(n, [](long long a, long long b){ return a + b; }, 0LL);
    for(int i = 0; i < n; i++){
        segx.update(hld.get(i), x[i]);
    }

    LazySegTree<S, op, e, F, mapping, composition, id> seg(n);
    vector<int> pidx(n);
    {
        long long sum = 0;
        auto query_sum = [&](int l, int r){
            sum += segx.query(l, r);
        };
        for(int i = 0; i < n; i++){
            for(int j : G[i]){
                int idx = max(hld.get(i), hld.get(j));
                sum = 0;
                pidx[hld.get(j)] = i;
                hld.subtree_query(j, query_sum);
                seg.update(idx, sum + L - a[i]);
            }
        }
    }

    while(q--){
        int t; cin >> t;
        if(t == 1){
            int a;
            long long b;
            cin >> a >> b;
            a--;

            long long d = b - segx[hld.get(a)];
            segx.update(hld.get(a), b);
            auto add_query = [&](int l, int r){
                seg.apply(l, r, d);
            };
            hld.path_query(root, a, add_query, false);
        }else{
            int c;
            cin >> c;
            c--;

            vector<pair<int, int>> path;
            auto query_min = [&](int l, int r){
                if(l == r){
                    return;
                }
                path.emplace_back(l, r);
            };

            if(L <= min(a[c], a[c + 1])){
                cout << L << "\n";
                continue;
            }
            int s = c + 1;
            if(a[c] < a[c + 1]) s = c;

            hld.path_query(s, root, query_min, false);
            reverse(path.begin(), path.end());

            int curr = -1;
            for(auto [l, r] : path){
                if(seg.query(l, r) > 0){
                    curr = l;
                }else{
                    int x = seg.min_left<f>(r);
                    if(l <= x && x < r){
                        curr = x;
                    }
                    break;
                }
            }

            long long ans = L;
            auto query_sum = [&](int l, int r){
                ans += segx.query(l, r);
            };
            if(curr == -1){
                hld.subtree_query(s, query_sum);
            }else{
                hld.subtree_query(pidx[curr], query_sum);
            }
            cout << ans << "\n";
        }
    }
}

yukicoder

結果

テストケース

ソースコード