Submission #1114669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114669		Wansur	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	2420 ms	727384 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 * 25];
int p[maxn * 25], c[maxn * 25];
int rx[maxn * 25];
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 push(int v, int tl, int tr) {
    if(tl == tr) return;
    int mid = tl + tr >> 1;
    pull(v * 2, p[v]);
    pull(v * 2 + 1, p[v]);
    dull(v * 2, rx[v]);
    dull(v * 2 + 1, rx[v]);
    p[v] = rx[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int x) {
    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(v * 2, tl, mid, l, r, x);
    upd(v * 2 + 1, mid + 1, tr, l, r, x);
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

void upd(int v, int tl, int tr, int pos, int x) {
    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(v * 2, tl, mid, pos, x);
    }
    else {
        upd(v * 2 + 1, mid + 1, tr, pos, x);
    }
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

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(v * 2, tl, mid, l, r, x);
    updrx(v * 2 + 1, mid + 1, tr, l, r, x);
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

void solve() {
    cin >> n >> k;
    int sum = 0;
    vector<array<int, 3>> Q;
    vector<int> v;
    while(n--) {
        int tp, pos, x;
        cin >> tp >> pos >> x;
        Q.push_back({tp, pos, x});
        for(int dx = -1; dx <= 1; dx++) {
            if(pos + dx >= 0 && tp == 1) {
                v.push_back(pos + dx);
            }
            if(pos + k + dx >= 0 && tp == 2) {
                v.push_back(pos + k + dx);
            }
            if(pos - k + dx >= 0 && tp == 2) {
                v.push_back(pos + k + dx);
            }
        }
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    m = (int) v.size();
    for(auto [tp, pos, x] : Q) {
        if(tp == 1) {
            pos = lower_bound(v.begin(), v.end(), pos) - v.begin();
            upd(1, 0, m, pos, x);
            sum += x;
        }
        else {
            int l = lower_bound(v.begin(), v.end(), pos - k) - v.begin(), r = lower_bound(v.begin(), v.end(), pos + k) - v.begin();
            upd(1, 0, m, l, r, x);
            updrx(1, 0, m, l, r - 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:57:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
sugar.cpp:57:9: warning: unused variable 'mid' [-Wunused-variable]
   57 |     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:72:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     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:87:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |     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:104:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     int mid = tl + tr >> 1;
      |               ~~~^~~~

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