Submission #1264909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264909		NHristov	Ants and Sugar (JOI22_sugar)	C++20	100 / 100	540 ms	72980 KiB

sugar

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

const int Q=5e5+5;

struct node {
    ll m[2][2], lazy, cnt;
} st[4*Q];

void app(int id, ll v) {
    for(int i=0; i<2; i++) {
        for(int q=0; q<2; q++) {
            st[id].m[i][q]-=v;
        }
    }
    st[id].lazy+=v;
    st[id].cnt+=v;
}

void push(int i) {
    if(!st[i].lazy)
        return;
    app(2*i, st[i].lazy);
    app(2*i+1, st[i].lazy);
    st[i].lazy=0;
}

void cmb(int i) {
    for(int a=0; a<2; a++) {
        for(int b=0; b<2; b++) {
            st[i].m[a][b]=max(st[2*i].m[a][0]+st[2*i+1].m[0][b],st[2*i].m[a][1]+st[2*i+1].m[1][b]+st[i].cnt);
        }
    }
    for(int a=0; a<2; a++) {
        st[i].m[a][0]=max(st[i].m[a][0], st[2*i].m[a][0]);
        st[i].m[0][a]=max(st[i].m[0][a], st[2*i+1].m[0][a]);
    }
}

void upda(int i, int l, int r, int p, ll v) {
    if(l==r) {
        for(int a=0; a<2; a++) {
            for(int b=0; b<2; b++) {
                st[i].m[a][b]+=v;
            }
        }
        return;
    }
    push(i);
    int m=l+r>>1;
    if(p<=m)
        upda(2*i, l, m, p, v);
    else
        upda(2*i+1, m+1, r, p, v);
    cmb(i);
}

void upds(int i, int l, int r, int ql, int qr, ll v) {
    if(l>qr||r<ql)
        return;
    if(ql<=l&&r<=qr) {
        app(i, v);
        return;
    }
    push(i);
    int m=l+r>>1;
    if(qr<=m)
        upds(2*i, l, m, ql, qr, v);
    else {
        if(ql>=m+1)
            upds(2*i+1, m+1, r, ql, qr, v);
        else {
            st[i].cnt+=v;
            upds(2*i, l, m, ql, qr, v);
            upds(2*i+1, m+1, r, ql, qr, v);
        }
    }
    cmb(i);
}

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

    int q, l;
    vector<array<ll, 3>> que;
    vector<int> p;
    cin >> q >> l;
    for(int i=1; i<=q; i++) {
        int t, x, a;
        cin >> t >> x >> a;
        if(t==1)
            p.push_back(x);
        que.push_back({t, x, a});
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    ll all=0;
    for(auto [t, x, a] : que) {
        if(t==1) {
            x=lower_bound(p.begin(), p.end(), x)-p.begin();
            upda(1, 0, p.size()-1, x, a);
            all+=a;
        }
        else {
            int ql=lower_bound(p.begin(), p.end(), x-l)-p.begin();
            int qr=upper_bound(p.begin(), p.end(), x+l)-p.begin()-1;
            if(ql<=qr)
                upds(1, 0, p.size()-1, ql, qr, a);
        }
        cout << all-max(0LL, st[1].m[0][0]) << endl;
    }

    return 0;
}

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