oj.uz

Submission #632954

# Submission time Handle Problem Language Result Execution time Memory
632954 2022-08-21T09:53:11 Z qwerasdfzxcl Ants and Sugar (JOI22_sugar) C++14
100 / 100
 2544 ms 260096 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll INF = 4e18;

struct P{
    ll x;
    int c;
    P(){}
    P(ll _x, int _c): x(_x), c(_c) {}
    bool operator < (const P &p) const{return x < p.x;}
    P operator + (const P &p) const{return P(x + p.x, c + p.c);}
};

struct Node{
    P ans[2][2];
    ll one[2][2];
    Node(){}
    Node(ll c, ll d){
        ans[0][0] = P(-c, 0);
        ans[0][1] = P(-INF, 0);
        ans[1][0] = P(-INF, 0);
        ans[1][1] = P(d, 1);

        one[0][0] = -c;
        one[0][1] = -INF;
        one[1][0] = -INF;
        one[1][1] = d;
    }

    void pcd(ll x){
        ans[0][0].x -= x;
        ans[1][1].x += x;
        one[0][0] -= x;
        one[1][1] += x;
    }

    void pd(ll x){
        assert(x<0);
        one[0][1] += x;
        one[1][0] += x;
        one[1][1] += x;

        for (int i=0;i<2;i++){
            for (int j=0;j<2;j++){
                assert(ans[i][j].c <= 2);
                ans[i][j].x += x * ans[i][j].c;

                if (ans[i][j].x < one[i][j]){
                    ans[i][j].x = one[i][j];
                    if (i || j) ans[i][j].c = 1;
                    else ans[i][j].c = 0;
                }
            }
        }
    }

    Node operator + (const Node &N) const{
        Node ret;
        for (int i=0;i<2;i++){
            for (int j=0;j<2;j++){
                ret.ans[i][j] = max(ans[i][j], N.ans[i][j]);
                ret.one[i][j] = max(one[i][j], N.one[i][j]);
                for (int k=0;k<2;k++) ret.ans[i][j] = max(ret.ans[i][j], ans[i][k] + N.ans[k^1][j]);
            }
        }

        ret.one[0][1] = max(ret.one[0][1], one[0][0] + N.one[1][1]);
        ret.one[1][0] = max(ret.one[1][0], one[1][1] + N.one[0][0]);
        return ret;
    }
};

struct Seg{
    Node tree[2202000];
    pair<ll, ll> lazy[2202000];
    void init(int i, int l, int r){
        lazy[i] = {0, 0};
        if (l==r) {tree[i] = Node(0, 0); return;}

        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void propagate(int i, int l, int r){
        if (lazy[i].first) tree[i].pcd(lazy[i].first);
        if (lazy[i].second) tree[i].pd(lazy[i].second);

        if (l!=r){
            lazy[i<<1].first += lazy[i].first;
            lazy[i<<1].second += lazy[i].second;

            lazy[i<<1|1].first += lazy[i].first;
            lazy[i<<1|1].second += lazy[i].second;
        }

        lazy[i] = {0, 0};
    }
    void update1(int i, int l, int r, int s, int e, ll x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i].first += x;
            propagate(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        update1(i<<1, l, m, s, e, x); update1(i<<1|1, m+1, r, s, e, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void update2(int i, int l, int r, int s, int e, ll x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i].second += x;
            propagate(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        update2(i<<1, l, m, s, e, x); update2(i<<1|1, m+1, r, s, e, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
}tree;

vector<int> C;
int T[500500], X[500500], A[500500], d;

int main(){
    int q;
    scanf("%d %d", &q, &d);
    for (int i=1;i<=q;i++){
        scanf("%d %d %d", T+i, X+i, A+i);
        C.push_back(X[i]);
        C.push_back(X[i]-1);
    }
    C.push_back(0);

    sort(C.begin(), C.end());
    C.erase(unique(C.begin(), C.end()), C.end());
    tree.init(1, 1, (int)C.size());

    ll cur = 0;
    for (int i=1;i<=q;i++){
        if (T[i]==1){
            int idx = lower_bound(C.begin(), C.end(), X[i]) - C.begin() + 1;
            tree.update1(1, 1, (int)C.size(), idx, (int)C.size(), A[i]);
            cur += A[i];
        }
        else{
            int idx1 = lower_bound(C.begin(), C.end(), X[i]-d) - C.begin() + 1;
            int idx2 = lower_bound(C.begin(), C.end(), X[i]+d) - C.begin() + 1;
            tree.update1(1, 1, (int)C.size(), idx2, (int)C.size(), -A[i]);
            tree.update2(1, 1, (int)C.size(), idx1, idx2-1, -A[i]);
        }

        ll ans = cur - max(tree.tree[1].ans[0][1].x, 0LL);
        printf("%lld\n", ans);
    }
    return 0;
}

Compilation message

sugar.cpp: In function 'int main()':
sugar.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     scanf("%d %d", &q, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sugar.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d %d %d", T+i, X+i, A+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 34772 KB Output is correct
2 Correct 15 ms 34732 KB Output is correct
3 Correct 13 ms 34772 KB Output is correct
4 Correct 13 ms 34772 KB Output is correct
5 Correct 17 ms 34780 KB Output is correct
6 Correct 17 ms 35652 KB Output is correct
7 Correct 17 ms 35308 KB Output is correct
8 Correct 17 ms 35140 KB Output is correct
9 Correct 16 ms 35164 KB Output is correct
10 Correct 24 ms 36528 KB Output is correct
11 Correct 21 ms 36460 KB Output is correct
12 Correct 26 ms 36476 KB Output is correct
13 Correct 20 ms 36520 KB Output is correct
14 Correct 21 ms 36436 KB Output is correct
15 Correct 21 ms 36432 KB Output is correct
16 Correct 20 ms 36436 KB Output is correct
17 Correct 19 ms 36464 KB Output is correct
18 Correct 25 ms 36464 KB Output is correct
19 Correct 22 ms 36436 KB Output is correct
20 Correct 17 ms 36436 KB Output is correct
21 Correct 22 ms 36536 KB Output is correct
22 Correct 19 ms 36428 KB Output is correct
23 Correct 24 ms 36452 KB Output is correct
24 Correct 19 ms 36476 KB Output is correct
25 Correct 25 ms 36520 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34788 KB Output is correct
2 Correct 14 ms 34760 KB Output is correct
3 Correct 13 ms 34688 KB Output is correct
4 Correct 1293 ms 152360 KB Output is correct
5 Correct 558 ms 96920 KB Output is correct
6 Correct 1549 ms 155568 KB Output is correct
7 Correct 576 ms 96908 KB Output is correct
8 Correct 1799 ms 159800 KB Output is correct
9 Correct 1206 ms 160264 KB Output is correct
10 Correct 1943 ms 159576 KB Output is correct
11 Correct 1158 ms 160284 KB Output is correct
12 Correct 487 ms 94452 KB Output is correct
13 Correct 735 ms 147572 KB Output is correct
14 Correct 1180 ms 156720 KB Output is correct
15 Correct 1160 ms 156744 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 34712 KB Output is correct
2 Correct 574 ms 94412 KB Output is correct
3 Correct 721 ms 147612 KB Output is correct
4 Correct 1148 ms 156900 KB Output is correct
5 Correct 1145 ms 156852 KB Output is correct
6 Correct 1511 ms 151976 KB Output is correct
7 Correct 102 ms 48640 KB Output is correct
8 Correct 788 ms 142704 KB Output is correct
9 Correct 1160 ms 147272 KB Output is correct
10 Correct 2166 ms 256456 KB Output is correct
11 Correct 2064 ms 256544 KB Output is correct
12 Correct 2088 ms 256580 KB Output is correct
13 Correct 2021 ms 256476 KB Output is correct
14 Correct 2117 ms 256636 KB Output is correct
15 Correct 1990 ms 256244 KB Output is correct
16 Correct 1977 ms 256496 KB Output is correct
17 Correct 2137 ms 256600 KB Output is correct
18 Correct 2425 ms 256628 KB Output is correct
19 Correct 2277 ms 256736 KB Output is correct
20 Correct 2333 ms 256668 KB Output is correct
21 Correct 2288 ms 256720 KB Output is correct
22 Correct 2389 ms 256684 KB Output is correct
23 Correct 2221 ms 256592 KB Output is correct
24 Correct 1196 ms 256704 KB Output is correct
25 Correct 1639 ms 256556 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 34772 KB Output is correct
2 Correct 15 ms 34732 KB Output is correct
3 Correct 13 ms 34772 KB Output is correct
4 Correct 13 ms 34772 KB Output is correct
5 Correct 17 ms 34780 KB Output is correct
6 Correct 17 ms 35652 KB Output is correct
7 Correct 17 ms 35308 KB Output is correct
8 Correct 17 ms 35140 KB Output is correct
9 Correct 16 ms 35164 KB Output is correct
10 Correct 24 ms 36528 KB Output is correct
11 Correct 21 ms 36460 KB Output is correct
12 Correct 26 ms 36476 KB Output is correct
13 Correct 20 ms 36520 KB Output is correct
14 Correct 21 ms 36436 KB Output is correct
15 Correct 21 ms 36432 KB Output is correct
16 Correct 20 ms 36436 KB Output is correct
17 Correct 19 ms 36464 KB Output is correct
18 Correct 25 ms 36464 KB Output is correct
19 Correct 22 ms 36436 KB Output is correct
20 Correct 17 ms 36436 KB Output is correct
21 Correct 22 ms 36536 KB Output is correct
22 Correct 19 ms 36428 KB Output is correct
23 Correct 24 ms 36452 KB Output is correct
24 Correct 19 ms 36476 KB Output is correct
25 Correct 25 ms 36520 KB Output is correct
26 Correct 16 ms 34788 KB Output is correct
27 Correct 14 ms 34760 KB Output is correct
28 Correct 13 ms 34688 KB Output is correct
29 Correct 1293 ms 152360 KB Output is correct
30 Correct 558 ms 96920 KB Output is correct
31 Correct 1549 ms 155568 KB Output is correct
32 Correct 576 ms 96908 KB Output is correct
33 Correct 1799 ms 159800 KB Output is correct
34 Correct 1206 ms 160264 KB Output is correct
35 Correct 1943 ms 159576 KB Output is correct
36 Correct 1158 ms 160284 KB Output is correct
37 Correct 487 ms 94452 KB Output is correct
38 Correct 735 ms 147572 KB Output is correct
39 Correct 1180 ms 156720 KB Output is correct
40 Correct 1160 ms 156744 KB Output is correct
41 Correct 13 ms 34712 KB Output is correct
42 Correct 574 ms 94412 KB Output is correct
43 Correct 721 ms 147612 KB Output is correct
44 Correct 1148 ms 156900 KB Output is correct
45 Correct 1145 ms 156852 KB Output is correct
46 Correct 1511 ms 151976 KB Output is correct
47 Correct 102 ms 48640 KB Output is correct
48 Correct 788 ms 142704 KB Output is correct
49 Correct 1160 ms 147272 KB Output is correct
50 Correct 2166 ms 256456 KB Output is correct
51 Correct 2064 ms 256544 KB Output is correct
52 Correct 2088 ms 256580 KB Output is correct
53 Correct 2021 ms 256476 KB Output is correct
54 Correct 2117 ms 256636 KB Output is correct
55 Correct 1990 ms 256244 KB Output is correct
56 Correct 1977 ms 256496 KB Output is correct
57 Correct 2137 ms 256600 KB Output is correct
58 Correct 2425 ms 256628 KB Output is correct
59 Correct 2277 ms 256736 KB Output is correct
60 Correct 2333 ms 256668 KB Output is correct
61 Correct 2288 ms 256720 KB Output is correct
62 Correct 2389 ms 256684 KB Output is correct
63 Correct 2221 ms 256592 KB Output is correct
64 Correct 1196 ms 256704 KB Output is correct
65 Correct 1639 ms 256556 KB Output is correct
66 Correct 1006 ms 148416 KB Output is correct
67 Correct 1248 ms 151428 KB Output is correct
68 Correct 1482 ms 154784 KB Output is correct
69 Correct 1362 ms 152928 KB Output is correct
70 Correct 2053 ms 259444 KB Output is correct
71 Correct 2039 ms 259468 KB Output is correct
72 Correct 2112 ms 259636 KB Output is correct
73 Correct 2074 ms 259572 KB Output is correct
74 Correct 2544 ms 253412 KB Output is correct
75 Correct 2439 ms 258952 KB Output is correct
76 Correct 1605 ms 258816 KB Output is correct
77 Correct 1514 ms 253516 KB Output is correct
78 Correct 1555 ms 253504 KB Output is correct
79 Correct 2150 ms 259808 KB Output is correct
80 Correct 1521 ms 253532 KB Output is correct
81 Correct 2145 ms 259760 KB Output is correct
82 Correct 1601 ms 253500 KB Output is correct
83 Correct 2427 ms 259912 KB Output is correct
84 Correct 1543 ms 253332 KB Output is correct
85 Correct 2483 ms 260064 KB Output is correct
86 Correct 1527 ms 253340 KB Output is correct
87 Correct 2485 ms 260096 KB Output is correct
88 Correct 1579 ms 253492 KB Output is correct
89 Correct 1698 ms 259776 KB Output is correct