Submission #1114652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114652		Wansur	Ants and Sugar (JOI22_sugar)	C++17	22 / 100	2001 ms	1048576 KiB

sugar

#include <bits/stdc++.h>
#define ent '\n'
#define int long long

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 12;
const int mod = 998244353;

int n, m, k;

struct asd {
    int dp[2][2];
    int rx, d;

    asd() {
        dp[0][0] = dp[1][0] = dp[0][1] = dp[1][1] = 0;
        rx = d = 0;
    }
};

asd merge(asd x, asd y) {
    asd ans;
    ans.rx = y.rx;
    ans.d = max(x.d, y.d);
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            ans.dp[i][j] = min(x.dp[i][1] + y.dp[1][j] - x.rx, min(x.dp[i][0], x.dp[i][1]) + min(y.dp[0][j], y.dp[1][j]));
        }
    }
    return ans;
}


asd t[maxn * 40];
int L[maxn * 40], R[maxn * 40];
int p[maxn * 40], c[maxn * 40];
int rx[maxn * 40];
int nv = 1;

void pull(int v, int x) {
    p[v] += x;
    t[v].dp[0][0] = min(t[v].dp[0][0] + x, 0ll);
    t[v].dp[1][1] += x;
    t[v].dp[0][1] += x;
    t[v].dp[1][0] += x;
    t[v].d += x;
}

void dull(int v, int x) {
    rx[v] += x;
    t[v].rx += x;
}

void create(int v, int tl, int mid, int tr) {
    if(!L[v]) {
        L[v] = ++nv;
        if(tl == mid) {
            t[L[v]].dp[0][1] = t[L[v]].dp[1][0] = 1e18;
        }
    }
    if(!R[v]) {
        R[v] = ++nv;
        if(mid + 1 == tr) {
            t[R[v]].dp[0][1] = t[R[v]].dp[1][0] = 1e18;
        }
    }
}

void push(int v, int tl, int tr) {
    if(tl == tr) return;
    int mid = tl + tr >> 1;
    create(v, tl, mid, tr);
    pull(L[v], p[v]);
    pull(R[v], p[v]);
    dull(L[v], rx[v]);
    dull(R[v], rx[v]);
    p[v] = rx[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int x) {
    assert(v < maxn * 40);
    if(tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        pull(v, x);
        return;
    }
    push(v, tl, tr);
    int mid = tl + tr >> 1;
    upd(L[v], tl, mid, l, r, x);
    upd(R[v], mid + 1, tr, l, r, x);
    t[v] = merge(t[L[v]], t[R[v]]);
}

void upd(int v, int tl, int tr, int pos, int x) {
    assert(v < maxn * 40);
    if(tl == tr) {
        c[v] += x;
        t[v].dp[0][0] = 0;
        t[v].dp[1][0] = t[v].dp[0][1] = 1e18;
        t[v].dp[1][1] = t[v].d - c[v];
        return;
    }
    push(v, tl, tr);
    int mid = tl + tr >> 1;
    if(pos <= mid) {
        upd(L[v], tl, mid, pos, x);
    }
    else {
        upd(R[v], mid + 1, tr, pos, x);
    }
    t[v] = merge(t[L[v]], t[R[v]]);
}

void updrx(int v, int tl, int tr, int l, int r, int x) {
    push(v, tl, tr);
    if(tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        dull(v, x);
        return;
    }
    int mid = tl + tr >> 1;
    updrx(L[v], tl, mid, l, r, x);
    updrx(R[v], mid + 1, tr, l, r, x);
    t[v] = merge(t[L[v]], t[R[v]]);
}

void solve() {
    cin >> n >> k;
    m = (1 << 30) - 1;
    int sum = 0;
    while(n--) {
        int tp, pos, x;
        cin >> tp >> pos >> x;
        if(tp == 1) {
            upd(1, 0, m, pos, x);
            sum += x;
        }
        else {
            upd(1, 0, m, pos - k, pos + k, x);
            updrx(1, 0, m, pos - k, pos + k - 1, x);
        }
        cout << sum + min({t[1].dp[0][0], t[1].dp[1][0], t[1].dp[0][1], t[1].dp[1][1]}) << ent;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;

    while(t--) {
        solve();
    }
}

Compilation message (stderr)

sugar.cpp: In function 'void push(long long int, long long int, long long int)':
sugar.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
sugar.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
sugar.cpp:90:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
sugar.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
sugar.cpp:106:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
sugar.cpp: In function 'void updrx(long long int, long long int, long long int, long long int, long long int, long long int)':
sugar.cpp:123:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |     int mid = tl + tr >> 1;
      |               ~~~^~~~

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