Submission #878062

#	Time	Username	Problem	Language	Result	Execution time	Memory
878062		abcvuitunggio	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	1006 ms	147256 KiB

sugar

#include <bits/stdc++.h>
#define int long long
using namespace std;
int st[4000001][2][2],lazy[4000001],lazy2[4000001],cnt[4000001];
int q,l,t[500001],x[500001],a[500001],s;
vector <int> ve;
void down(int node, int l, int r){
    if (l==r)
        return;
    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++){
            st[node<<1][i][j]+=lazy[node];
            st[node<<1|1][i][j]+=lazy[node];
        }
    lazy[node<<1]+=lazy[node];
    lazy[node<<1|1]+=lazy[node];
    lazy[node]=0;
    cnt[node<<1]+=lazy2[node];
    cnt[node<<1|1]+=lazy2[node];
    lazy2[node<<1]+=lazy2[node];
    lazy2[node<<1|1]+=lazy2[node];
    lazy2[node]=0;
}
void update(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||l>r)
        return;
    if (l>=u&&r<=v){
        for (int i=0;i<2;i++)
            for (int j=0;j<2;j++)
                st[node][i][j]+=val;
        lazy[node]+=val;
        cnt[node]+=val;
        lazy2[node]+=val;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    if (mid>=u&&mid<v)
        cnt[node]+=val;
    update(node<<1,l,mid,u,v,val);
    update(node<<1|1,mid+1,r,u,v,val);
    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++)
            st[node][i][j]=max(st[node<<1][i][0]+st[node<<1|1][0][j],st[node<<1][i][1]+st[node<<1|1][1][j]-cnt[node]);
    for (int i=0;i<2;i++){
        st[node][i][0]=max(st[node][i][0],st[node<<1][i][0]);
        st[node][0][i]=max(st[node][0][i],st[node<<1|1][0][i]);
    }
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> q >> l;
    for (int i=0;i<q;i++){
        cin >> t[i] >> x[i] >> a[i];
        if (t[i]==1)
            ve.push_back(x[i]);
        else{
            ve.push_back(x[i]-l);
            ve.push_back(x[i]+l);
        }
    }
    sort(ve.begin(),ve.end());
    ve.resize(unique(ve.begin(),ve.end())-ve.begin());
    for (int i=0;i<q;i++){
        if (t[i]==1){
            s+=a[i];
            int pos=lower_bound(ve.begin(),ve.end(),x[i])-ve.begin();
            update(1,0,ve.size()-1,pos,pos,a[i]);
        }
        else{
            int u=lower_bound(ve.begin(),ve.end(),x[i]-l)-ve.begin();
            int v=lower_bound(ve.begin(),ve.end(),x[i]+l)-ve.begin();
            update(1,0,ve.size()-1,u,v,-a[i]);
        }
        cout << s-max(st[1][0][0],0LL) << '\n';
    }
}

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