oj.uz

Submission #1114653

# Submission time Handle Problem Language Result Execution time Memory
1114653 2024-11-19T10:21:50 Z Wansur Ants and Sugar (JOI22_sugar) C++17
22 / 100
 2017 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 465 ms 940620 KB Output is correct
2 Correct 477 ms 940404 KB Output is correct
3 Correct 479 ms 940616 KB Output is correct
4 Correct 516 ms 940552 KB Output is correct
5 Correct 522 ms 940616 KB Output is correct
6 Correct 532 ms 940912 KB Output is correct
7 Correct 526 ms 940832 KB Output is correct
8 Correct 533 ms 940872 KB Output is correct
9 Correct 517 ms 940676 KB Output is correct
10 Correct 557 ms 950060 KB Output is correct
11 Correct 571 ms 950308 KB Output is correct
12 Correct 541 ms 950348 KB Output is correct
13 Correct 559 ms 951368 KB Output is correct
14 Correct 561 ms 952672 KB Output is correct
15 Correct 542 ms 952648 KB Output is correct
16 Correct 505 ms 945120 KB Output is correct
17 Correct 515 ms 944968 KB Output is correct
18 Correct 514 ms 944868 KB Output is correct
19 Correct 509 ms 950304 KB Output is correct
20 Correct 506 ms 944984 KB Output is correct
21 Correct 530 ms 949832 KB Output is correct
22 Correct 516 ms 944968 KB Output is correct
23 Correct 535 ms 949524 KB Output is correct
24 Correct 544 ms 944968 KB Output is correct
25 Correct 528 ms 946760 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 940420 KB Output is correct
2 Correct 527 ms 940616 KB Output is correct
3 Correct 520 ms 940616 KB Output is correct
4 Correct 1548 ms 980456 KB Output is correct
5 Correct 919 ms 967240 KB Output is correct
6 Correct 1555 ms 987560 KB Output is correct
7 Correct 1024 ms 967376 KB Output is correct
8 Correct 1989 ms 996288 KB Output is correct
9 Correct 1541 ms 996528 KB Output is correct
10 Correct 2017 ms 995716 KB Output is correct
11 Correct 1419 ms 998544 KB Output is correct
12 Correct 931 ms 963912 KB Output is correct
13 Correct 1152 ms 972700 KB Output is correct
14 Correct 1525 ms 993296 KB Output is correct
15 Correct 1542 ms 993356 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 940476 KB Output is correct
2 Correct 976 ms 965444 KB Output is correct
3 Correct 1113 ms 972912 KB Output is correct
4 Correct 1451 ms 993296 KB Output is correct
5 Correct 1433 ms 993172 KB Output is correct
6 Correct 1597 ms 987464 KB Output is correct
7 Correct 615 ms 955208 KB Output is correct
8 Correct 1133 ms 978276 KB Output is correct
9 Correct 1419 ms 983716 KB Output is correct
10 Runtime error 786 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 465 ms 940620 KB Output is correct
2 Correct 477 ms 940404 KB Output is correct
3 Correct 479 ms 940616 KB Output is correct
4 Correct 516 ms 940552 KB Output is correct
5 Correct 522 ms 940616 KB Output is correct
6 Correct 532 ms 940912 KB Output is correct
7 Correct 526 ms 940832 KB Output is correct
8 Correct 533 ms 940872 KB Output is correct
9 Correct 517 ms 940676 KB Output is correct
10 Correct 557 ms 950060 KB Output is correct
11 Correct 571 ms 950308 KB Output is correct
12 Correct 541 ms 950348 KB Output is correct
13 Correct 559 ms 951368 KB Output is correct
14 Correct 561 ms 952672 KB Output is correct
15 Correct 542 ms 952648 KB Output is correct
16 Correct 505 ms 945120 KB Output is correct
17 Correct 515 ms 944968 KB Output is correct
18 Correct 514 ms 944868 KB Output is correct
19 Correct 509 ms 950304 KB Output is correct
20 Correct 506 ms 944984 KB Output is correct
21 Correct 530 ms 949832 KB Output is correct
22 Correct 516 ms 944968 KB Output is correct
23 Correct 535 ms 949524 KB Output is correct
24 Correct 544 ms 944968 KB Output is correct
25 Correct 528 ms 946760 KB Output is correct
26 Correct 527 ms 940420 KB Output is correct
27 Correct 527 ms 940616 KB Output is correct
28 Correct 520 ms 940616 KB Output is correct
29 Correct 1548 ms 980456 KB Output is correct
30 Correct 919 ms 967240 KB Output is correct
31 Correct 1555 ms 987560 KB Output is correct
32 Correct 1024 ms 967376 KB Output is correct
33 Correct 1989 ms 996288 KB Output is correct
34 Correct 1541 ms 996528 KB Output is correct
35 Correct 2017 ms 995716 KB Output is correct
36 Correct 1419 ms 998544 KB Output is correct
37 Correct 931 ms 963912 KB Output is correct
38 Correct 1152 ms 972700 KB Output is correct
39 Correct 1525 ms 993296 KB Output is correct
40 Correct 1542 ms 993356 KB Output is correct
41 Correct 532 ms 940476 KB Output is correct
42 Correct 976 ms 965444 KB Output is correct
43 Correct 1113 ms 972912 KB Output is correct
44 Correct 1451 ms 993296 KB Output is correct
45 Correct 1433 ms 993172 KB Output is correct
46 Correct 1597 ms 987464 KB Output is correct
47 Correct 615 ms 955208 KB Output is correct
48 Correct 1133 ms 978276 KB Output is correct
49 Correct 1419 ms 983716 KB Output is correct
50 Runtime error 786 ms 1048576 KB Execution killed with signal 9
51 Halted 0 ms 0 KB -