oj.uz

Submission #1114656

# Submission time Handle Problem Language Result Execution time Memory
1114656 2024-11-19T10:24:01 Z Wansur Ants and Sugar (JOI22_sugar) C++17
22 / 100
 2058 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 * 20];
int L[maxn * 20], R[maxn * 20];
int p[maxn * 20], c[maxn * 20];
int rx[maxn * 20];
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) {
    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) {
    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:89:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     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:104:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     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:121:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |     int mid = tl + tr >> 1;
      |               ~~~^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 471372 KB Output is correct
2 Correct 250 ms 471384 KB Output is correct
3 Correct 252 ms 471372 KB Output is correct
4 Correct 245 ms 471380 KB Output is correct
5 Correct 233 ms 471368 KB Output is correct
6 Correct 231 ms 471608 KB Output is correct
7 Correct 224 ms 471624 KB Output is correct
8 Correct 227 ms 471488 KB Output is correct
9 Correct 216 ms 471624 KB Output is correct
10 Correct 235 ms 480592 KB Output is correct
11 Correct 257 ms 481104 KB Output is correct
12 Correct 244 ms 481352 KB Output is correct
13 Correct 248 ms 481096 KB Output is correct
14 Correct 246 ms 483444 KB Output is correct
15 Correct 251 ms 483656 KB Output is correct
16 Correct 254 ms 476184 KB Output is correct
17 Correct 257 ms 475888 KB Output is correct
18 Correct 254 ms 475748 KB Output is correct
19 Correct 249 ms 481120 KB Output is correct
20 Correct 243 ms 475720 KB Output is correct
21 Correct 256 ms 480676 KB Output is correct
22 Correct 251 ms 475756 KB Output is correct
23 Correct 263 ms 480344 KB Output is correct
24 Correct 239 ms 475724 KB Output is correct
25 Correct 248 ms 477676 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 471536 KB Output is correct
2 Correct 232 ms 471516 KB Output is correct
3 Correct 239 ms 471376 KB Output is correct
4 Correct 1241 ms 512200 KB Output is correct
5 Correct 670 ms 498096 KB Output is correct
6 Correct 1324 ms 517964 KB Output is correct
7 Correct 662 ms 498248 KB Output is correct
8 Correct 1693 ms 526664 KB Output is correct
9 Correct 1229 ms 529576 KB Output is correct
10 Correct 1688 ms 526596 KB Output is correct
11 Correct 1156 ms 527556 KB Output is correct
12 Correct 639 ms 495804 KB Output is correct
13 Correct 761 ms 506184 KB Output is correct
14 Correct 1159 ms 524100 KB Output is correct
15 Correct 1210 ms 524004 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 471368 KB Output is correct
2 Correct 646 ms 494684 KB Output is correct
3 Correct 855 ms 503648 KB Output is correct
4 Correct 1217 ms 524208 KB Output is correct
5 Correct 1133 ms 524028 KB Output is correct
6 Correct 1357 ms 519080 KB Output is correct
7 Correct 326 ms 486216 KB Output is correct
8 Correct 854 ms 509000 KB Output is correct
9 Correct 1177 ms 514744 KB Output is correct
10 Runtime error 2058 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 234 ms 471372 KB Output is correct
2 Correct 250 ms 471384 KB Output is correct
3 Correct 252 ms 471372 KB Output is correct
4 Correct 245 ms 471380 KB Output is correct
5 Correct 233 ms 471368 KB Output is correct
6 Correct 231 ms 471608 KB Output is correct
7 Correct 224 ms 471624 KB Output is correct
8 Correct 227 ms 471488 KB Output is correct
9 Correct 216 ms 471624 KB Output is correct
10 Correct 235 ms 480592 KB Output is correct
11 Correct 257 ms 481104 KB Output is correct
12 Correct 244 ms 481352 KB Output is correct
13 Correct 248 ms 481096 KB Output is correct
14 Correct 246 ms 483444 KB Output is correct
15 Correct 251 ms 483656 KB Output is correct
16 Correct 254 ms 476184 KB Output is correct
17 Correct 257 ms 475888 KB Output is correct
18 Correct 254 ms 475748 KB Output is correct
19 Correct 249 ms 481120 KB Output is correct
20 Correct 243 ms 475720 KB Output is correct
21 Correct 256 ms 480676 KB Output is correct
22 Correct 251 ms 475756 KB Output is correct
23 Correct 263 ms 480344 KB Output is correct
24 Correct 239 ms 475724 KB Output is correct
25 Correct 248 ms 477676 KB Output is correct
26 Correct 235 ms 471536 KB Output is correct
27 Correct 232 ms 471516 KB Output is correct
28 Correct 239 ms 471376 KB Output is correct
29 Correct 1241 ms 512200 KB Output is correct
30 Correct 670 ms 498096 KB Output is correct
31 Correct 1324 ms 517964 KB Output is correct
32 Correct 662 ms 498248 KB Output is correct
33 Correct 1693 ms 526664 KB Output is correct
34 Correct 1229 ms 529576 KB Output is correct
35 Correct 1688 ms 526596 KB Output is correct
36 Correct 1156 ms 527556 KB Output is correct
37 Correct 639 ms 495804 KB Output is correct
38 Correct 761 ms 506184 KB Output is correct
39 Correct 1159 ms 524100 KB Output is correct
40 Correct 1210 ms 524004 KB Output is correct
41 Correct 231 ms 471368 KB Output is correct
42 Correct 646 ms 494684 KB Output is correct
43 Correct 855 ms 503648 KB Output is correct
44 Correct 1217 ms 524208 KB Output is correct
45 Correct 1133 ms 524028 KB Output is correct
46 Correct 1357 ms 519080 KB Output is correct
47 Correct 326 ms 486216 KB Output is correct
48 Correct 854 ms 509000 KB Output is correct
49 Correct 1177 ms 514744 KB Output is correct
50 Runtime error 2058 ms 1048576 KB Execution killed with signal 9
51 Halted 0 ms 0 KB -