oj.uz

Submission #708374

# Submission time Handle Problem Language Result Execution time Memory
708374 2023-03-11T16:07:06 Z doowey Ants and Sugar (JOI22_sugar) C++14
100 / 100
 3497 ms 108664 KB 
#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
const int N = (int)5e5 + 10;
int typ[N];
int X[N];
int A[N];
 
struct Node{
    ll dp[2][2][2]; // [start][end][x_cnt]
    ll lazy_x;
    ll lazy_both;
};
 
void upd(ll &a, ll b){
    a = max(a, b);
}
 
Node make_node(){
    Node r;
    for(int i = 0 ; i < 2; i ++ ){
        for(int j = 0; j < 2; j ++ ){
            for(int k = 0 ;k < 2; k ++ ){
                r.dp[i][j][k] = -(ll)1e18;
            }
        }
    }
    r.lazy_x = 0ll;
    r.lazy_both = 0ll;
    return r;
}
 
const Node D = make_node();
 
Node unite(Node aa, Node bb){
    Node res = aa;
    int cum;
    for(int st = 0 ; st < 2; st ++ ){
        for(int en = 0; en < 2; en ++ ){
            for(int p = 0; p < 2; p ++ ){
                for(int q = 0; q < 2; q ++ ){
                    upd(res.dp[st][en][1], aa.dp[st][0][p] + bb.dp[1][en][q]);
                    upd(res.dp[st][en][1], aa.dp[st][1][p] + bb.dp[0][en][q]);
                }
                upd(res.dp[st][en][p], bb.dp[st][en][p]);
            }
        }
    }
    return res;
}
 
Node T[N * 4 + 512];
 
void push(int node, int cl, int cr){
    for(int f = 0; f < 2; f ++ ){
        for(int c = 0; c < 2; c ++ ){
            if(f == 0) T[node].dp[f][f][c] -= T[node].lazy_both;
            else T[node].dp[f][f][c] += T[node].lazy_both;
            for(int s = 0 ; s < 2; s ++ ){
                T[node].dp[f][s][c] += (c + (f + s == 2)) * 1ll * T[node].lazy_x;
            }
        }
    }
    if(cl != cr){
        T[node * 2].lazy_x += T[node].lazy_x;
        T[node * 2 + 1].lazy_x += T[node].lazy_x;
        T[node * 2].lazy_both += T[node].lazy_both;
        T[node * 2 + 1].lazy_both += T[node].lazy_both;
    }
    T[node].lazy_x = T[node].lazy_both = 0;
}
 
void update(int node, int cl, int cr, int tl, int tr, int Xi, int Yi){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(Xi == Yi){
            T[node].lazy_both = Xi;
        }
        else{
            T[node].lazy_x = Xi;
        }
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2ll;
    update(node * 2, cl, mid, tl, tr, Xi, Yi);
    update(node * 2 + 1, mid + 1, cr, tl, tr, Xi, Yi);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
 
int k;
vector<int> posi;
void perform_update(int tl, int tr, int Xi, int Yi){
    int ii = lower_bound(posi.begin(), posi.end(), tl) - posi.begin();
    int jj = lower_bound(posi.begin(), posi.end(), tr + 1) - posi.begin();
    jj -- ;
    //cout << ii << " " << jj << " | " << Xi << " " << Yi << "\n";
    if(ii <= jj)
        update(1, 0, k - 1, ii, jj, Xi, Yi);
}
 
void build(int node, int cl, int cr){
    T[node] = D;
    if(cl == cr){
        T[node].dp[0][0][0] = 0;
        T[node].dp[0][1][1] = 0;
        T[node].dp[1][1][0] = 0;
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
 
ll get_max(){
    ll V = 0ll;
    V = max(V, T[1].dp[0][1][1]);
    return V;
}
 
int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int q, d;
    cin >> q >> d;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> typ[iq] >> X[iq] >> A[iq];
        posi.push_back(X[iq]);
    }
    sort(posi.begin(), posi.end());
    posi.resize(unique(posi.begin(), posi.end()) - posi.begin());
    k = posi.size();
    
    build(1, 0, k - 1);
    ll ants = 0ll;
    for(int iq = 1; iq <= q; iq ++ ){
        if(typ[iq] == 1){
            perform_update(X[iq] + 1, (int)1e9, A[iq], A[iq]);
            perform_update(X[iq], X[iq], A[iq], 0);
            ants += A[iq];
        }
        else{
            perform_update(X[iq] + d + 1, (int)1e9, -A[iq], -A[iq]);
            perform_update(X[iq] - d, X[iq] + d, -A[iq], 0);
        }
        cout << ants - get_max() << "\n";
 
    }
    return 0;
}

Compilation message

sugar.cpp: In function 'Node unite(Node, Node)':
sugar.cpp:46:9: warning: unused variable 'cum' [-Wunused-variable]
   46 |     int cum;
      |         ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 6 ms 720 KB Output is correct
7 Correct 5 ms 648 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 9 ms 1108 KB Output is correct
11 Correct 9 ms 1108 KB Output is correct
12 Correct 9 ms 1108 KB Output is correct
13 Correct 10 ms 1172 KB Output is correct
14 Correct 9 ms 1112 KB Output is correct
15 Correct 9 ms 1108 KB Output is correct
16 Correct 9 ms 1108 KB Output is correct
17 Correct 10 ms 1072 KB Output is correct
18 Correct 9 ms 1108 KB Output is correct
19 Correct 9 ms 1108 KB Output is correct
20 Correct 9 ms 1132 KB Output is correct
21 Correct 10 ms 1148 KB Output is correct
22 Correct 12 ms 1136 KB Output is correct
23 Correct 10 ms 1108 KB Output is correct
24 Correct 9 ms 1108 KB Output is correct
25 Correct 8 ms 1108 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1653 ms 54248 KB Output is correct
5 Correct 933 ms 50488 KB Output is correct
6 Correct 1966 ms 73144 KB Output is correct
7 Correct 938 ms 50552 KB Output is correct
8 Correct 2391 ms 99436 KB Output is correct
9 Correct 2041 ms 101956 KB Output is correct
10 Correct 2420 ms 101652 KB Output is correct
11 Correct 2081 ms 102020 KB Output is correct
12 Correct 865 ms 50888 KB Output is correct
13 Correct 1251 ms 94172 KB Output is correct
14 Correct 2009 ms 98716 KB Output is correct
15 Correct 2005 ms 98648 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 850 ms 48428 KB Output is correct
3 Correct 1192 ms 91372 KB Output is correct
4 Correct 2017 ms 96160 KB Output is correct
5 Correct 2001 ms 98480 KB Output is correct
6 Correct 1877 ms 96172 KB Output is correct
7 Correct 115 ms 6824 KB Output is correct
8 Correct 915 ms 49972 KB Output is correct
9 Correct 1358 ms 52668 KB Output is correct
10 Correct 2510 ms 98212 KB Output is correct
11 Correct 2559 ms 98188 KB Output is correct
12 Correct 2499 ms 98644 KB Output is correct
13 Correct 2514 ms 98304 KB Output is correct
14 Correct 2617 ms 98632 KB Output is correct
15 Correct 2461 ms 98220 KB Output is correct
16 Correct 2498 ms 98500 KB Output is correct
17 Correct 2728 ms 98132 KB Output is correct
18 Correct 2888 ms 97836 KB Output is correct
19 Correct 2876 ms 105332 KB Output is correct
20 Correct 3292 ms 105240 KB Output is correct
21 Correct 3246 ms 105352 KB Output is correct
22 Correct 3282 ms 105216 KB Output is correct
23 Correct 3032 ms 105196 KB Output is correct
24 Correct 1795 ms 105460 KB Output is correct
25 Correct 2074 ms 105456 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 6 ms 720 KB Output is correct
7 Correct 5 ms 648 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 9 ms 1108 KB Output is correct
11 Correct 9 ms 1108 KB Output is correct
12 Correct 9 ms 1108 KB Output is correct
13 Correct 10 ms 1172 KB Output is correct
14 Correct 9 ms 1112 KB Output is correct
15 Correct 9 ms 1108 KB Output is correct
16 Correct 9 ms 1108 KB Output is correct
17 Correct 10 ms 1072 KB Output is correct
18 Correct 9 ms 1108 KB Output is correct
19 Correct 9 ms 1108 KB Output is correct
20 Correct 9 ms 1132 KB Output is correct
21 Correct 10 ms 1148 KB Output is correct
22 Correct 12 ms 1136 KB Output is correct
23 Correct 10 ms 1108 KB Output is correct
24 Correct 9 ms 1108 KB Output is correct
25 Correct 8 ms 1108 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1653 ms 54248 KB Output is correct
30 Correct 933 ms 50488 KB Output is correct
31 Correct 1966 ms 73144 KB Output is correct
32 Correct 938 ms 50552 KB Output is correct
33 Correct 2391 ms 99436 KB Output is correct
34 Correct 2041 ms 101956 KB Output is correct
35 Correct 2420 ms 101652 KB Output is correct
36 Correct 2081 ms 102020 KB Output is correct
37 Correct 865 ms 50888 KB Output is correct
38 Correct 1251 ms 94172 KB Output is correct
39 Correct 2009 ms 98716 KB Output is correct
40 Correct 2005 ms 98648 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 850 ms 48428 KB Output is correct
43 Correct 1192 ms 91372 KB Output is correct
44 Correct 2017 ms 96160 KB Output is correct
45 Correct 2001 ms 98480 KB Output is correct
46 Correct 1877 ms 96172 KB Output is correct
47 Correct 115 ms 6824 KB Output is correct
48 Correct 915 ms 49972 KB Output is correct
49 Correct 1358 ms 52668 KB Output is correct
50 Correct 2510 ms 98212 KB Output is correct
51 Correct 2559 ms 98188 KB Output is correct
52 Correct 2499 ms 98644 KB Output is correct
53 Correct 2514 ms 98304 KB Output is correct
54 Correct 2617 ms 98632 KB Output is correct
55 Correct 2461 ms 98220 KB Output is correct
56 Correct 2498 ms 98500 KB Output is correct
57 Correct 2728 ms 98132 KB Output is correct
58 Correct 2888 ms 97836 KB Output is correct
59 Correct 2876 ms 105332 KB Output is correct
60 Correct 3292 ms 105240 KB Output is correct
61 Correct 3246 ms 105352 KB Output is correct
62 Correct 3282 ms 105216 KB Output is correct
63 Correct 3032 ms 105196 KB Output is correct
64 Correct 1795 ms 105460 KB Output is correct
65 Correct 2074 ms 105456 KB Output is correct
66 Correct 1317 ms 55556 KB Output is correct
67 Correct 1571 ms 58052 KB Output is correct
68 Correct 1925 ms 102264 KB Output is correct
69 Correct 1770 ms 59692 KB Output is correct
70 Correct 2559 ms 108136 KB Output is correct
71 Correct 2591 ms 108300 KB Output is correct
72 Correct 2709 ms 108308 KB Output is correct
73 Correct 3040 ms 108308 KB Output is correct
74 Correct 3411 ms 102084 KB Output is correct
75 Correct 3008 ms 107560 KB Output is correct
76 Correct 2942 ms 107564 KB Output is correct
77 Correct 3110 ms 102128 KB Output is correct
78 Correct 2864 ms 102100 KB Output is correct
79 Correct 2894 ms 108312 KB Output is correct
80 Correct 2683 ms 102068 KB Output is correct
81 Correct 2972 ms 108444 KB Output is correct
82 Correct 2730 ms 101924 KB Output is correct
83 Correct 3497 ms 108580 KB Output is correct
84 Correct 2718 ms 102096 KB Output is correct
85 Correct 3361 ms 108560 KB Output is correct
86 Correct 2670 ms 102152 KB Output is correct
87 Correct 3114 ms 108664 KB Output is correct
88 Correct 2689 ms 101936 KB Output is correct
89 Correct 2412 ms 108540 KB Output is correct