oj.uz

Submission #1114652

# Submission time Handle Problem Language Result Execution time Memory
1114652 2024-11-19T10:20:16 Z Wansur Ants and Sugar (JOI22_sugar) C++17
22 / 100
 2001 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 604 ms 940572 KB Output is correct
2 Correct 512 ms 940508 KB Output is correct
3 Correct 536 ms 940616 KB Output is correct
4 Correct 535 ms 940616 KB Output is correct
5 Correct 545 ms 940440 KB Output is correct
6 Correct 557 ms 940872 KB Output is correct
7 Correct 534 ms 940812 KB Output is correct
8 Correct 536 ms 940860 KB Output is correct
9 Correct 556 ms 940872 KB Output is correct
10 Correct 536 ms 949840 KB Output is correct
11 Correct 571 ms 950344 KB Output is correct
12 Correct 544 ms 950292 KB Output is correct
13 Correct 563 ms 950264 KB Output is correct
14 Correct 537 ms 952676 KB Output is correct
15 Correct 570 ms 952848 KB Output is correct
16 Correct 584 ms 945060 KB Output is correct
17 Correct 503 ms 944956 KB Output is correct
18 Correct 530 ms 944932 KB Output is correct
19 Correct 536 ms 950088 KB Output is correct
20 Correct 537 ms 944888 KB Output is correct
21 Correct 557 ms 949884 KB Output is correct
22 Correct 536 ms 944968 KB Output is correct
23 Correct 550 ms 949576 KB Output is correct
24 Correct 561 ms 945212 KB Output is correct
25 Correct 587 ms 946808 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 940616 KB Output is correct
2 Correct 555 ms 940588 KB Output is correct
3 Correct 542 ms 940484 KB Output is correct
4 Correct 1565 ms 980664 KB Output is correct
5 Correct 993 ms 967240 KB Output is correct
6 Correct 1576 ms 987140 KB Output is correct
7 Correct 940 ms 967496 KB Output is correct
8 Correct 2001 ms 995884 KB Output is correct
9 Correct 1523 ms 996144 KB Output is correct
10 Correct 1953 ms 995876 KB Output is correct
11 Correct 1491 ms 996348 KB Output is correct
12 Correct 914 ms 964016 KB Output is correct
13 Correct 1090 ms 972872 KB Output is correct
14 Correct 1505 ms 993264 KB Output is correct
15 Correct 1529 ms 993200 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 940460 KB Output is correct
2 Correct 940 ms 963912 KB Output is correct
3 Correct 1133 ms 972872 KB Output is correct
4 Correct 1525 ms 993388 KB Output is correct
5 Correct 1437 ms 993372 KB Output is correct
6 Correct 1640 ms 987284 KB Output is correct
7 Correct 636 ms 955208 KB Output is correct
8 Correct 1103 ms 978400 KB Output is correct
9 Correct 1512 ms 983596 KB Output is correct
10 Runtime error 837 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 604 ms 940572 KB Output is correct
2 Correct 512 ms 940508 KB Output is correct
3 Correct 536 ms 940616 KB Output is correct
4 Correct 535 ms 940616 KB Output is correct
5 Correct 545 ms 940440 KB Output is correct
6 Correct 557 ms 940872 KB Output is correct
7 Correct 534 ms 940812 KB Output is correct
8 Correct 536 ms 940860 KB Output is correct
9 Correct 556 ms 940872 KB Output is correct
10 Correct 536 ms 949840 KB Output is correct
11 Correct 571 ms 950344 KB Output is correct
12 Correct 544 ms 950292 KB Output is correct
13 Correct 563 ms 950264 KB Output is correct
14 Correct 537 ms 952676 KB Output is correct
15 Correct 570 ms 952848 KB Output is correct
16 Correct 584 ms 945060 KB Output is correct
17 Correct 503 ms 944956 KB Output is correct
18 Correct 530 ms 944932 KB Output is correct
19 Correct 536 ms 950088 KB Output is correct
20 Correct 537 ms 944888 KB Output is correct
21 Correct 557 ms 949884 KB Output is correct
22 Correct 536 ms 944968 KB Output is correct
23 Correct 550 ms 949576 KB Output is correct
24 Correct 561 ms 945212 KB Output is correct
25 Correct 587 ms 946808 KB Output is correct
26 Correct 570 ms 940616 KB Output is correct
27 Correct 555 ms 940588 KB Output is correct
28 Correct 542 ms 940484 KB Output is correct
29 Correct 1565 ms 980664 KB Output is correct
30 Correct 993 ms 967240 KB Output is correct
31 Correct 1576 ms 987140 KB Output is correct
32 Correct 940 ms 967496 KB Output is correct
33 Correct 2001 ms 995884 KB Output is correct
34 Correct 1523 ms 996144 KB Output is correct
35 Correct 1953 ms 995876 KB Output is correct
36 Correct 1491 ms 996348 KB Output is correct
37 Correct 914 ms 964016 KB Output is correct
38 Correct 1090 ms 972872 KB Output is correct
39 Correct 1505 ms 993264 KB Output is correct
40 Correct 1529 ms 993200 KB Output is correct
41 Correct 529 ms 940460 KB Output is correct
42 Correct 940 ms 963912 KB Output is correct
43 Correct 1133 ms 972872 KB Output is correct
44 Correct 1525 ms 993388 KB Output is correct
45 Correct 1437 ms 993372 KB Output is correct
46 Correct 1640 ms 987284 KB Output is correct
47 Correct 636 ms 955208 KB Output is correct
48 Correct 1103 ms 978400 KB Output is correct
49 Correct 1512 ms 983596 KB Output is correct
50 Runtime error 837 ms 1048576 KB Execution killed with signal 9
51 Halted 0 ms 0 KB -