Submission #1275869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275869		Icelast	Ants and Sugar (JOI22_sugar)	C++20	0 / 100	2800 ms	1114112 KiB

sugar

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
template <class Info, class Tag>
struct ImplicitLazySegmentTree {
    struct Node {
        Info info = Info();
        Tag tag = Tag();
        int ln = 0, rn = 0;
    };

    ll n;
    vector<Node> nodes;

    ImplicitLazySegmentTree(ll n) : n(n), nodes(2) {
        nodes[1].info.makeDefault(0, n);
    }

    void apply(int p, const Tag &t) {
        nodes[p].info.apply(t);
        nodes[p].tag.apply(t);
    }
    void pull(int p) {
        nodes[p].info = nodes[nodes[p].ln].info + nodes[nodes[p].rn].info;
    }
    void push(int p) {
        apply(nodes[p].ln, nodes[p].tag);
        apply(nodes[p].rn, nodes[p].tag);
        nodes[p].tag = Tag();
    }
    void newNode(int &aug, int l, int r)  {
        aug = nodes.size();
        nodes.push_back(nodes[0]);
        nodes.back().info.makeDefault(l, r);
    }

    template <class T>
    void modify(int i, const T &val) {
        auto dfs = [&](auto self, int p, int l, int r) -> void {
            if (l + 1 == r) {
                nodes[p].info = val;
                return;
            }
            int m = (l + r) >> 1;
            if (nodes[p].ln == 0) newNode(nodes[p].ln, l, m);
            if (nodes[p].rn == 0) newNode(nodes[p].rn, m, r);
            push(p);
            if (i < m) self(self, nodes[p].ln, l, m);
            else self(self, nodes[p].rn, m, r);
            pull(p);
        };
        dfs(dfs, 1, 0, n);
    }

    void rangeApply(int ql, int qr, const Tag &t) {
        auto dfs = [&](auto self, int p, int l, int r) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) return apply(p, t);
            int m = (l + r) >> 1;
            if (nodes[p].ln == 0) newNode(nodes[p].ln, l, m);
            if (nodes[p].rn == 0) newNode(nodes[p].rn, m, r);
            push(p);
            self(self, nodes[p].ln, l, m);
            self(self, nodes[p].rn, m, r);
            pull(p);
        };
        dfs(dfs, 1, 0, n);
    }

    Info rangeQuery(int ql, int qr) {
        Info res = Info();
        auto dfs = [&](auto self, int p, int l, int r, Tag t) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) {
                Info info = nodes[p].info;
                if (p == 0) info.makeDefault(l, r);
                info.apply(t);
                res = res + info;
                return;
            }
            int m = (l + r) >> 1;
            t.apply(nodes[p].tag);
            self(self, nodes[p].ln, l, m, t);
            self(self, nodes[p].rn, m, r, t);
        };
        dfs(dfs, 1, 0, n, Tag());
        return res;
    }

    template <class F>
    int findFirst(int ql, int qr, F &&pred) {
        Info res = Info();
        auto dfs = [&](auto self, int p, int l, int r, Tag t) -> int {
            if (r <= ql || qr <= l) return -1;
            Info info = nodes[p].info;
            if (p == 0) info.makeDefault(l, r);
            info.apply(t);
            if (ql <= l && r <= qr && !pred(info)) return -1;
            if (l + 1 == r) return l;
            int m = (l + r) >> 1;
            t.apply(nodes[p].tag);
            int get = self(self, nodes[p].ln, l, m, t);
            if (get == -1) get = self(self, nodes[p].rn, m, r, t);
            return get;
        };
        return dfs(dfs, 1, 0, n, Tag());
    }
};

struct Tag {
    ll add = 0;
    void apply(const Tag &t) {
        add += t.add;
    }
};
struct Info2 {
    ll sum = 0;
    void makeDefault(int l, int r) {}
    void apply(const Tag &t) {
        sum += t.add;
    }
    Info2 operator+(const Info2 &b) const {
        return {sum + b.sum};
    }
};
struct Info {
    ll f[2][2] = {{0, INF}, {INF, INF}};
    ll b = 0;
    bool is_I = true;
    void makeDefault(int l, int r) {is_I = false;}
    void apply(const Tag &t) {

    }
    Info operator+(const Info &b) const {
        Info a = *this, res;
        if(a.is_I) return b;
        if(b.is_I) return a;
        res.is_I = false;
        res.b = a.b + b.b;
        for(int i = 0; i <= 1; i++){
            for(int j = 0; j <= 1; j++){
                for(int k = 0; k <= 1;  k++){
                    res.f[i][j] = min(res.f[i][j], a.f[i][k] + b.f[k][j]);
                }
            }
        }
        res.f[1][0] = min(res.f[1][0], a.b + b.f[1][0]);
        res.f[0][1] = min(res.f[0][1], a.f[0][1] + b.b);
        res.f[1][1] = min({res.f[1][1], a.f[1][1] + b.b, b.f[1][1] + a.b});
        return res;
    }
};

void solve(){
    int q, L;
    cin >> q >> L;
    ll N = 2e9;
    ImplicitLazySegmentTree<Info, Tag> T(N+1);
    ImplicitLazySegmentTree<Info2, Tag> Tb(N+1);
    map<int, ll> Ta;
    ll sumV1 = 0;
    for(int i = 1; i <= q; i++){
        ll t, x, a;
        cin >> t >> x >> a;
        if(t == 1){
            Tb.rangeApply(x, x+1, {a});
            Info I;
            I.is_I = false;
            I.b = Tb.rangeQuery(x, x+1).sum;
            T.modify(x, I);
            cout << 0 << "\n";
        }else{
            Ta[x] += a;
            sumV1 += a;
            Info I;
            I.is_I = false;
            ll A = Ta[x];
            I.b = -A + Tb.rangeQuery(x, x+1).sum;
            I.f[0][0] = min(0LL, -A + Tb.rangeQuery(max(0LL, x-L), min(N+1, x+L+1)).sum);
            I.f[1][0] = -A + Tb.rangeQuery(x, min(N+1, x+L+1)).sum;
            I.f[0][1] = -A + Tb.rangeQuery(max(0LL, x-L), x+1).sum;
            T.modify(x, I);
            cout << sumV1 + T.rangeQuery(0, N+1).f[0][0] << "\n";
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52