Submission #722778

#	Time	Username	Problem	Language	Result	Execution time	Memory
722778		fatemetmhr	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	1945 ms	120552 KiB

sugar

// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  5e5   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  2e6   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int lg    =  19;
const ll  inf   =  1e18;

int lim, m, a[maxn5], ty[maxn5], x[maxn5];
vector <int> av;
ll sum = 0;

struct segst{

    ll dp[2][2], lazy, tomerge;
    segst(){
        dp[0][1] = dp[1][0] = dp[0][0] = -inf;
        dp[1][1] = 0;
        lazy = tomerge = 0;
    }

} seg[maxnt];

inline void output(int v){
    cout << "checking " << v << ' ' << seg[v].tomerge << ' ' << seg[v].dp[0][0] << ' ' << seg[v].dp[0][1];
    cout << ' ' << seg[v].dp[1][0] << ' ' << seg[v].dp[1][1] << '\n';
}

inline segst operator +(segst a, segst b){
    segst ret;
    ret.tomerge = b.tomerge;
    ret.dp[1][1] = -inf;
    for(int i = 0; i < 2; i++){
        ret.dp[i][0] = max({ret.dp[i][0], a.dp[i][0], a.dp[i][1]});
        ret.dp[0][i] = max({ret.dp[0][i], b.dp[0][i], b.dp[1][i]});
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                for(int l = 0; l < 2; l++)
                    ret.dp[i][j] = max(ret.dp[i][j], a.dp[i][k] + b.dp[l][j] + ((k && l) * a.tomerge));
    }
    return ret;
}

inline void lahaz(int v, ll val){
    seg[v].lazy += val;
    seg[v].tomerge -= val;
    for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++)
        seg[v].dp[i][j] += val;
}

inline void shift(int v){
    lahaz(v * 2, seg[v].lazy);
    lahaz(v * 2 + 1, seg[v].lazy);
    seg[v].lazy = 0;
}


void add(int l, int r, int lq, int rq, int val1, int val2, int v){
    if(rq <= l || r <= lq)
        return;
    if(lq <= l && r <= rq){
        if(r - l == 1){
            seg[v].tomerge += val2;
            seg[v].dp[1][1] += val1;
        }
        else
            lahaz(v, val1);
        return;
    }
    int mid = (l + r) >> 1; shift(v);
    add(l, mid, lq, rq, val1, val2, v * 2);
    add(mid, r, lq, rq, val1, val2, v * 2 + 1);
    seg[v] = seg[v * 2] + seg[v * 2 + 1];
}

void upd(int l, int r, int id, int val, int v){
    if(r - l == 1){
        seg[v].dp[1][1] += val;
        return;
    }
    int mid = (l + r) >> 1; shift(v);
    if(id < mid)
        upd(l, mid, id, val, v * 2);
    else
        upd(mid, r, id, val, v * 2 + 1);
    seg[v] = seg[v * 2] + seg[v * 2 + 1];
    //output(v);
}

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

    int n; cin >> n >> lim;
    for(int i = 0; i < n; i++){
        cin >> ty[i] >> x[i] >> a[i];
        ty[i]--;
        av.pb(x[i]);
    }
    sort(all(av));
    av.resize(unique(all(av)) - av.begin());
    m = av.size();
    sum = 0;
    for(int i = 0; i < n; i++){
        int pt = lower_bound(all(av), x[i]) - av.begin();
        if(ty[i]){
            sum += a[i];
            upd(0, m, pt, a[i], 1);
        }
        else{
            int l = lower_bound(all(av), x[i] - lim) - av.begin();
            int r = upper_bound(all(av), x[i] + lim) - av.begin();
            add(0, m, r - 1, r, -a[i], 0, 1);
            if(l < r - 1)
                add(0, m, l, r - 1, -a[i], a[i], 1);
        }
        cout << sum - max({0LL, seg[1].dp[0][0], seg[1].dp[1][0], seg[1].dp[0][1], seg[1].dp[1][1]}) << '\n';
    }
}

/*
20 268886972
1 984472666 733463744
1 478477245 94817772
1 242536956 330762563
1 65794782 319137646
1 320548477 937296140
1 815011370 938193848
1 565184190 917533785
1 245417414 534089975
1 529908772 977043962
1 603891865 700935654
2 167042244 479827216
2 173921297 798343455
2 916159596 810126726
2 999299355 465535307
2 965968070 501768990
2 936073643 174976034
2 832859952 778072072
2 955489596 704853861
2 246733786 382428992
2 227669861 390905006
*/

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