Submission #722631

#	Time	Username	Problem	Language	Result	Execution time	Memory
722631		fatemetmhr	Ants and Sugar (JOI22_sugar)	C++17	6 / 100	4102 ms	819732 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, lef[maxn5], rig[maxn5], a[maxn5], ty[maxn5];
int segl[maxnt][2][2], segr[maxnt][2][2], x[maxn5];
ll dp[maxnt][2][2];
vector <int> av;

struct segmnt_tree{

    struct node{
        ll mx[2], lazy[2];
        int id[2];
        node(){
            lazy[0] = lazy[1] = mx[0] = mx[1] = 0;
        }
    } seg[maxn5 << 1];

    int newnode = 2, chil[maxn5 << 1];


    void build(int l, int r, int v){
        seg[v].id[0] = seg[v].id[1] = l;
        if(r - l == 1)
            return;
        int mid = (l + r) >> 1;
        chil[v] = newnode;
        newnode += 2;
        build(l, mid, chil[v]);
        build(mid, r, chil[v] + 1);
    }

    void add(int l, int r, int lq, int rq, int val, int ty, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            seg[v].lazy[ty] += val;
            seg[v].mx[ty] += val;
            return;
        }
        int mid = (l + r) >> 1;
        add(l, mid, lq, rq, val, ty, chil[v]);
        add(mid, r, lq, rq, val, ty, chil[v] + 1);
        int good = chil[v] + (seg[chil[v]].mx[ty] < seg[chil[v] + 1].mx[ty]);
        seg[v].mx[ty] = seg[good].mx[ty] + seg[v].lazy[ty];
        seg[v].id[ty] = seg[good].id[ty];
    }

    pair <ll, int> get_max(int l, int r, int lq, int rq, int ty, int v){
        if(rq <= l || r <= lq)
            return {-inf, 0};
        if(lq <= l && r <= rq)
            return {seg[v].mx[ty], seg[v].id[ty]};
        int mid = (l + r) >> 1;
        auto ans = max(get_max(l, mid, lq, rq, ty, chil[v]), get_max(mid, r, lq, rq, ty, chil[v] + 1));
        return {ans.fi + seg[v].lazy[ty], ans.se};
    }


} seg[lg];

void add(int l, int r, int id, int val, int ty, int v, int h){
    if(r - l == 1){
        dp[v][ty][ty] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        add(l, mid, id, val, ty, v * 2, h + 1);
        seg[h].add(0, m, l, id, -val, ty, 1);
    }
    else{
        add(mid, r, id, val, ty, v * 2 + 1, h + 1);
        seg[h].add(0, m, lef[id], mid, -val, ty ^ 1, 1);
    }
    for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++){
        ll val1 = dp[v * 2][i][0] + dp[v * 2 + 1][0][j], val2 = dp[v * 2][i][1] + dp[v * 2 + 1][1][j];
        ll val3 = -inf, val4 = -inf;
        int ind1, ind2;
        if(rig[segr[v * 2][i][0]] < segl[v * 2 + 1][1][j]){
            auto ans = seg[h].get_max(0, m, segr[v * 2][i][0], min(mid, lef[segl[v * 2 + 1][1][j]]), 0, 1);
            val3 = dp[v * 2][i][0] + dp[v * 2 + 1][1][j] + ans.fi;
            ind1 = ans.se;
        }
        if(rig[segr[v * 2][i][1]] < segl[v * 2 + 1][0][j]){
            auto ans = seg[h].get_max(0, m, segr[v * 2][i][1], min(mid, lef[segl[v * 2 + 1][0][j]]), 1, 1);
            val4 = dp[v * 2][i][1] + dp[v * 2 + 1][0][j] + ans.fi;
            //cout << "hmm " << ans.fi << ' ' << ans.se << '\n';
            ind2 = ans.se;
        }
        dp[v][i][j] = max({val1, val2, val3, val4});
        if(val1 >= max({val2, val3, val4})){
            segl[v][i][j] = segl[v * 2][i][0];
            segr[v][i][j] = segr[v * 2 + 1][0][j];
            if(segl[v * 2][i][0] == mid - 1)
                segl[v][i][j] = segl[v * 2 + 1][0][j];
            if(segr[v * 2 + 1][0][j] == mid)
                segr[v][i][j] = segr[v * 2][i][0];
        }
        else if(val2 >= max(val3, val4)){
            segl[v][i][j] = segl[v * 2][i][1];
            segr[v][i][j] = segr[v * 2 + 1][1][j];
            if(segl[v * 2][i][1] == mid - 1)
                segl[v][i][j] = segl[v * 2 + 1][1][j];
            if(segr[v * 2 + 1][1][j] == mid)
                segr[v][i][j] = segr[v * 2][i][1];
        }
        else if(val3 > val4){
            segl[v][i][j] = segl[v * 2][i][0];
            segr[v][i][j] = segr[v * 2 + 1][1][j];
            if(segl[v * 2][i][0] == mid - 1)
                segl[v][i][j] = ind1;
            if(segr[v * 2 + 1][1][j] == mid)
                segr[v][i][j] = rig[ind1] + 1;
        }
        else{
            segl[v][i][j] = segl[v * 2][i][1];
            segr[v][i][j] = segr[v * 2 + 1][0][j];
            if(segl[v * 2][i][1] == mid - 1)
                segl[v][i][j] = ind2;
            if(segr[v * 2 + 1][0][j] == mid)
                segr[v][i][j] = rig[ind2] + 1;
        }
        /*
        cout << "well done " << l << ' ' << r << ' ' << id << ' ' << v << ' ' << i << ' ' << j << ' ' << dp[v][i][j];
        cout << ' ' << val1 << ' ' << val2 << ' ' << val3 << ' ' << val4 << '\n';
        cout << segl[v][i][j] << ' ' << segr[v][i][j] << '\n';
        //*/
    }

    return;
}

void build(int l, int r, int v){
    segl[v][0][0] = segl[v][1][1] = r - 1;
    segr[v][0][0] = segr[v][1][1] = l;
    dp[v][0][1] = dp[v][1][0] = -inf;
    if(r - l == 1)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, v * 2);
    build(mid, r, v * 2 + 1);
}

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();
    for(int i = 0; i < lg; i++)
        seg[i].build(0, m, 1);
    build(0, m, 1);
    for(int i = 0; i < m; i++){
        lef[i] = lower_bound(all(av), av[i] - lim) - av.begin();
        rig[i] = upper_bound(all(av), av[i] + lim) - av.begin() - 1;
    }
    ll sum = 0;
    for(int i = 0; i < n; i++){
        sum += a[i];
        int pt = lower_bound(all(av), x[i]) - av.begin();
        add(0, m, pt, a[i], ty[i], 1, 0);
        cout << sum - max({dp[1][0][0], dp[1][1][0], dp[1][1][1], dp[1][0][1]}) << '\n';
    }
}

/*
6 6
2 27 12
2 9 11
1 36 10
2 39 4
2 14 9
2 33 7
2 38 20
2 0 20
2 25 16
1 14 3
1 13 19
2 6 4
2 15 6
2 33 4
1 12 11
1 44 1
2 17 14
2 12 19
1 48 18
2 30 16
*/

Compilation message (stderr)

sugar.cpp: In function 'void add(int, int, int, int, int, int, int)':
sugar.cpp:144:41: warning: 'ind2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |                 segr[v][i][j] = rig[ind2] + 1;
      |                                 ~~~~~~~~^
sugar.cpp:136:41: warning: 'ind1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |                 segr[v][i][j] = rig[ind1] + 1;
      |                                 ~~~~~~~~^
sugar.cpp: In function 'int main()':
sugar.cpp:144:41: warning: 'ind2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |                 segr[v][i][j] = rig[ind2] + 1;
      |                                 ~~~~~~~~^
sugar.cpp:101:19: note: 'ind2' was declared here
  101 |         int ind1, ind2;
      |                   ^~~~
sugar.cpp:136:41: warning: 'ind1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |                 segr[v][i][j] = rig[ind1] + 1;
      |                                 ~~~~~~~~^
sugar.cpp:101:13: note: 'ind1' was declared here
  101 |         int ind1, ind2;
      |             ^~~~

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