oj.uz

Submission #1114668

# Submission time Handle Problem Language Result Execution time Memory
1114668 2024-11-19T10:38:30 Z Wansur Ants and Sugar (JOI22_sugar) C++17
22 / 100
 1845 ms 1048576 KB 
#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 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 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) {
                v.push_back(pos + dx);
            }
            if(pos + k + dx >= 0) {
                v.push_back(pos + k + dx);
            }
            if(pos - k + dx >= 0) {
                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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 941384 KB Output is correct
2 Correct 512 ms 941228 KB Output is correct
3 Correct 486 ms 941384 KB Output is correct
4 Correct 476 ms 941384 KB Output is correct
5 Correct 476 ms 941640 KB Output is correct
6 Correct 509 ms 941868 KB Output is correct
7 Correct 520 ms 941848 KB Output is correct
8 Correct 518 ms 941648 KB Output is correct
9 Correct 509 ms 941628 KB Output is correct
10 Correct 531 ms 943508 KB Output is correct
11 Correct 472 ms 943148 KB Output is correct
12 Correct 495 ms 943148 KB Output is correct
13 Correct 492 ms 943148 KB Output is correct
14 Correct 522 ms 942816 KB Output is correct
15 Correct 492 ms 942872 KB Output is correct
16 Correct 517 ms 943280 KB Output is correct
17 Correct 523 ms 943304 KB Output is correct
18 Correct 533 ms 943308 KB Output is correct
19 Correct 534 ms 943260 KB Output is correct
20 Correct 536 ms 943148 KB Output is correct
21 Correct 539 ms 943308 KB Output is correct
22 Correct 540 ms 943152 KB Output is correct
23 Correct 544 ms 942936 KB Output is correct
24 Correct 486 ms 942652 KB Output is correct
25 Correct 503 ms 942908 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 941456 KB Output is correct
2 Correct 472 ms 941308 KB Output is correct
3 Correct 516 ms 941384 KB Output is correct
4 Correct 1465 ms 1015728 KB Output is correct
5 Correct 887 ms 985836 KB Output is correct
6 Correct 1486 ms 1022044 KB Output is correct
7 Correct 861 ms 985840 KB Output is correct
8 Correct 1845 ms 1030536 KB Output is correct
9 Correct 1363 ms 1031124 KB Output is correct
10 Correct 1816 ms 1030528 KB Output is correct
11 Correct 1323 ms 1031048 KB Output is correct
12 Correct 767 ms 982240 KB Output is correct
13 Correct 955 ms 1007792 KB Output is correct
14 Correct 1308 ms 1030340 KB Output is correct
15 Correct 1298 ms 1030340 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 941284 KB Output is correct
2 Correct 822 ms 981720 KB Output is correct
3 Correct 989 ms 1007652 KB Output is correct
4 Correct 1329 ms 1030340 KB Output is correct
5 Correct 1266 ms 1030340 KB Output is correct
6 Correct 1441 ms 1017256 KB Output is correct
7 Correct 559 ms 956692 KB Output is correct
8 Correct 1102 ms 990700 KB Output is correct
9 Correct 1308 ms 1007068 KB Output is correct
10 Runtime error 1000 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 941384 KB Output is correct
2 Correct 512 ms 941228 KB Output is correct
3 Correct 486 ms 941384 KB Output is correct
4 Correct 476 ms 941384 KB Output is correct
5 Correct 476 ms 941640 KB Output is correct
6 Correct 509 ms 941868 KB Output is correct
7 Correct 520 ms 941848 KB Output is correct
8 Correct 518 ms 941648 KB Output is correct
9 Correct 509 ms 941628 KB Output is correct
10 Correct 531 ms 943508 KB Output is correct
11 Correct 472 ms 943148 KB Output is correct
12 Correct 495 ms 943148 KB Output is correct
13 Correct 492 ms 943148 KB Output is correct
14 Correct 522 ms 942816 KB Output is correct
15 Correct 492 ms 942872 KB Output is correct
16 Correct 517 ms 943280 KB Output is correct
17 Correct 523 ms 943304 KB Output is correct
18 Correct 533 ms 943308 KB Output is correct
19 Correct 534 ms 943260 KB Output is correct
20 Correct 536 ms 943148 KB Output is correct
21 Correct 539 ms 943308 KB Output is correct
22 Correct 540 ms 943152 KB Output is correct
23 Correct 544 ms 942936 KB Output is correct
24 Correct 486 ms 942652 KB Output is correct
25 Correct 503 ms 942908 KB Output is correct
26 Correct 473 ms 941456 KB Output is correct
27 Correct 472 ms 941308 KB Output is correct
28 Correct 516 ms 941384 KB Output is correct
29 Correct 1465 ms 1015728 KB Output is correct
30 Correct 887 ms 985836 KB Output is correct
31 Correct 1486 ms 1022044 KB Output is correct
32 Correct 861 ms 985840 KB Output is correct
33 Correct 1845 ms 1030536 KB Output is correct
34 Correct 1363 ms 1031124 KB Output is correct
35 Correct 1816 ms 1030528 KB Output is correct
36 Correct 1323 ms 1031048 KB Output is correct
37 Correct 767 ms 982240 KB Output is correct
38 Correct 955 ms 1007792 KB Output is correct
39 Correct 1308 ms 1030340 KB Output is correct
40 Correct 1298 ms 1030340 KB Output is correct
41 Correct 522 ms 941284 KB Output is correct
42 Correct 822 ms 981720 KB Output is correct
43 Correct 989 ms 1007652 KB Output is correct
44 Correct 1329 ms 1030340 KB Output is correct
45 Correct 1266 ms 1030340 KB Output is correct
46 Correct 1441 ms 1017256 KB Output is correct
47 Correct 559 ms 956692 KB Output is correct
48 Correct 1102 ms 990700 KB Output is correct
49 Correct 1308 ms 1007068 KB Output is correct
50 Runtime error 1000 ms 1048576 KB Execution killed with signal 9
51 Halted 0 ms 0 KB -