oj.uz

Submission #847066

# Submission time Handle Problem Language Result Execution time Memory
847066 2023-09-09T05:40:29 Z eltu0815 Ants and Sugar (JOI22_sugar) C++14
100 / 100
 1492 ms 142100 KB 
#include <bits/stdc++.h>
#define MAX 500005
#define MOD 998244353
#define INF (ll)(1e18)
#define inf (1987654321)

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef complex<long double> cpx;
constexpr long double PI = acos(-1);

int q, L;
int chk[MAX];
pair<int, pii> query[MAX];

struct Node {
    ll v, sum;
    ll dp[2][2];
    ll lz1, lz2;
    Node() {
        v = sum = 0;
        dp[0][0] = dp[1][0] = dp[0][1] = dp[1][1] = -INF;
        lz1 = lz2 = 0;
    }
};

Node Merge(Node l, Node r) {
    Node ret = Node(); ret.v = r.v; ret.sum = l.sum + r.sum + l.v;
    for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) {
        if(i == 0) ret.dp[i][j] = max(ret.dp[i][j], max(r.dp[0][j], r.dp[1][j]));
        if(j == 0) ret.dp[i][j] = max(ret.dp[i][j], max(l.dp[i][0], l.dp[i][1]));
        
        // dp[0][0] of leaf nodes means INF - (lazy updates of lz1), which indicates the number of sugar in the i-th coordinate
        // we have to merge sets that satisfy |S| > 0, but we can also merge the set |S| == 0 and the set |S| > 0 together
        // note that the set whose |S| is 0 always 
        // when there's no ant in the left node, we can make dp[1][i] = -(the number of sugar) + r.dp[1][i] = -l.dp[0][0] + INF + r.dp[1][i];
        if(i == 1) ret.dp[i][j] = max(ret.dp[i][j], l.sum + r.dp[1][j] + l.v);
        if(j == 1) ret.dp[i][j] = max(ret.dp[i][j], l.dp[i][1] + r.sum + l.v);
    
        for(int a = 0; a <= 1; ++a) for(int b = 0; b <= 1; ++b) {
            ret.dp[i][j] = max(ret.dp[i][j], l.dp[i][a] + r.dp[b][j] + (a & b) * l.v);
        }
    }
    return ret;
}

Node seg[MAX << 2];
void init(int str, int ed, int node) {
    if(str == ed) return;
    int mid = str + ed >> 1;
    init(str, mid, node << 1);
    init(mid + 1, ed, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

void lazyProp(int str, int ed, int node) {
    if(seg[node].lz1) {
        seg[node].sum += seg[node].lz1;
        for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) seg[node].dp[i][j] += seg[node].lz1;
        if(str != ed) {
            seg[node << 1].lz1 += seg[node].lz1;
            seg[node << 1 | 1].lz1 += seg[node].lz1;
        }
        seg[node].lz1 = 0;
    }
    
    if(seg[node].lz2) {
        seg[node].v += seg[node].lz2;
        if(str != ed) {
            seg[node << 1].lz2 += seg[node].lz2;
            seg[node << 1 | 1].lz2 += seg[node].lz2;
        }
        seg[node].lz2 = 0;
    }
}

void update1(int str, int ed, int left, int right, ll val, int node) {
    lazyProp(str, ed, node);
    if(str > right || ed < left) return;
    if(left <= str && ed <= right) {
        seg[node].lz1 = val;
        lazyProp(str, ed, node);
        return;
    }
    int mid = str + ed >> 1;
    update1(str, mid, left, right, val, node << 1);
    update1(mid + 1, ed, left, right, val, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

void update2(int str, int ed, int left, int right, ll val, int node) {
    lazyProp(str, ed, node);
    if(str > right || ed < left) return;
    if(left <= str && ed <= right) {
        seg[node].lz2 = val;
        lazyProp(str, ed, node);
        return;
    }
    int mid = str + ed >> 1;
    update2(str, mid, left, right, val, node << 1);
    update2(mid + 1, ed, left, right, val, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

void update3(int str, int ed, int idx, ll val, int node) {
    lazyProp(str, ed, node);
    if(str > idx || ed < idx) return;
    if(str == ed) {
        seg[node].dp[1][1] += val;
        return;
    }
    int mid = str + ed >> 1;
    update3(str, mid, idx, val, node << 1);
    update3(mid + 1, ed, idx, val, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

ll max_query(int str, int ed, int node) {
    lazyProp(str, ed, node);
    return max(0ll, seg[1].dp[0][0]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> q >> L;
    for(int i = 1; i <= q; ++i) cin >> query[i].first >> query[i].second.first >> query[i].second.second;
    
    vector<int> tmp; tmp.push_back(-1000000005); tmp.push_back(2000000005);
    for(int i = 1; i <= q; ++i) if(query[i].first == 1) tmp.push_back(query[i].second.first);
    sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    
    int n = tmp.size() - 1;
    init(0, n, 1); ll A = 0, B = 0;
    for(int i = 1; i <= q; ++i) {
        if(query[i].first == 1) {
            int idx = lower_bound(tmp.begin(), tmp.end(), query[i].second.first) - tmp.begin();
            A += query[i].second.second;
            if(chk[idx] == 0) chk[idx] = 1, update3(0, n, idx, 1ll * query[i].second.second + INF, 1);
            else update3(0, n, idx, query[i].second.second, 1);
        }
        else {
            int l = lower_bound(tmp.begin(), tmp.end(), query[i].second.first - L) - tmp.begin();
            int r = upper_bound(tmp.begin(), tmp.end(), query[i].second.first + L) - tmp.begin() - 1;
            B += query[i].second.second;
            if(l <= r) update1(0, n, l, r, -query[i].second.second, 1);
            if(l < r) update2(0, n, l, r - 1, query[i].second.second, 1);
        }
        cout << A - max_query(0, n, 1) << '\n';
    }
    return 0;
}

Compilation message

sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:52:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update1(int, int, int, int, ll, int)':
sugar.cpp:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update2(int, int, int, int, ll, int)':
sugar.cpp:101:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update3(int, int, int, ll, int)':
sugar.cpp:114:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |     int mid = str + ed >> 1;
      |               ~~~~^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 125784 KB Output is correct
2 Correct 17 ms 125784 KB Output is correct
3 Correct 19 ms 125784 KB Output is correct
4 Correct 17 ms 125776 KB Output is correct
5 Correct 17 ms 125784 KB Output is correct
6 Correct 19 ms 125784 KB Output is correct
7 Correct 20 ms 125784 KB Output is correct
8 Correct 18 ms 125776 KB Output is correct
9 Correct 18 ms 125776 KB Output is correct
10 Correct 19 ms 125784 KB Output is correct
11 Correct 19 ms 125784 KB Output is correct
12 Correct 21 ms 125784 KB Output is correct
13 Correct 21 ms 125788 KB Output is correct
14 Correct 19 ms 125688 KB Output is correct
15 Correct 18 ms 125656 KB Output is correct
16 Correct 20 ms 125784 KB Output is correct
17 Correct 20 ms 125788 KB Output is correct
18 Correct 20 ms 125784 KB Output is correct
19 Correct 20 ms 125784 KB Output is correct
20 Correct 21 ms 125784 KB Output is correct
21 Correct 22 ms 125784 KB Output is correct
22 Correct 20 ms 125776 KB Output is correct
23 Correct 24 ms 126088 KB Output is correct
24 Correct 20 ms 125612 KB Output is correct
25 Correct 23 ms 125776 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 125984 KB Output is correct
2 Correct 17 ms 125784 KB Output is correct
3 Correct 17 ms 125784 KB Output is correct
4 Correct 582 ms 138036 KB Output is correct
5 Correct 379 ms 134392 KB Output is correct
6 Correct 708 ms 138992 KB Output is correct
7 Correct 382 ms 134732 KB Output is correct
8 Correct 891 ms 140528 KB Output is correct
9 Correct 816 ms 141592 KB Output is correct
10 Correct 808 ms 140492 KB Output is correct
11 Correct 800 ms 141516 KB Output is correct
12 Correct 355 ms 132816 KB Output is correct
13 Correct 489 ms 133836 KB Output is correct
14 Correct 841 ms 137856 KB Output is correct
15 Correct 822 ms 137916 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 125784 KB Output is correct
2 Correct 349 ms 132816 KB Output is correct
3 Correct 492 ms 133864 KB Output is correct
4 Correct 793 ms 137932 KB Output is correct
5 Correct 798 ms 138116 KB Output is correct
6 Correct 594 ms 136416 KB Output is correct
7 Correct 43 ms 128080 KB Output is correct
8 Correct 308 ms 132660 KB Output is correct
9 Correct 539 ms 133684 KB Output is correct
10 Correct 814 ms 138032 KB Output is correct
11 Correct 1002 ms 137852 KB Output is correct
12 Correct 858 ms 138196 KB Output is correct
13 Correct 753 ms 137736 KB Output is correct
14 Correct 867 ms 137736 KB Output is correct
15 Correct 560 ms 137504 KB Output is correct
16 Correct 712 ms 137952 KB Output is correct
17 Correct 1150 ms 138016 KB Output is correct
18 Correct 1373 ms 138264 KB Output is correct
19 Correct 1294 ms 137792 KB Output is correct
20 Correct 1271 ms 137888 KB Output is correct
21 Correct 1404 ms 137756 KB Output is correct
22 Correct 1491 ms 137840 KB Output is correct
23 Correct 1492 ms 137920 KB Output is correct
24 Correct 1326 ms 138292 KB Output is correct
25 Correct 1364 ms 137928 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 125784 KB Output is correct
2 Correct 17 ms 125784 KB Output is correct
3 Correct 19 ms 125784 KB Output is correct
4 Correct 17 ms 125776 KB Output is correct
5 Correct 17 ms 125784 KB Output is correct
6 Correct 19 ms 125784 KB Output is correct
7 Correct 20 ms 125784 KB Output is correct
8 Correct 18 ms 125776 KB Output is correct
9 Correct 18 ms 125776 KB Output is correct
10 Correct 19 ms 125784 KB Output is correct
11 Correct 19 ms 125784 KB Output is correct
12 Correct 21 ms 125784 KB Output is correct
13 Correct 21 ms 125788 KB Output is correct
14 Correct 19 ms 125688 KB Output is correct
15 Correct 18 ms 125656 KB Output is correct
16 Correct 20 ms 125784 KB Output is correct
17 Correct 20 ms 125788 KB Output is correct
18 Correct 20 ms 125784 KB Output is correct
19 Correct 20 ms 125784 KB Output is correct
20 Correct 21 ms 125784 KB Output is correct
21 Correct 22 ms 125784 KB Output is correct
22 Correct 20 ms 125776 KB Output is correct
23 Correct 24 ms 126088 KB Output is correct
24 Correct 20 ms 125612 KB Output is correct
25 Correct 23 ms 125776 KB Output is correct
26 Correct 17 ms 125984 KB Output is correct
27 Correct 17 ms 125784 KB Output is correct
28 Correct 17 ms 125784 KB Output is correct
29 Correct 582 ms 138036 KB Output is correct
30 Correct 379 ms 134392 KB Output is correct
31 Correct 708 ms 138992 KB Output is correct
32 Correct 382 ms 134732 KB Output is correct
33 Correct 891 ms 140528 KB Output is correct
34 Correct 816 ms 141592 KB Output is correct
35 Correct 808 ms 140492 KB Output is correct
36 Correct 800 ms 141516 KB Output is correct
37 Correct 355 ms 132816 KB Output is correct
38 Correct 489 ms 133836 KB Output is correct
39 Correct 841 ms 137856 KB Output is correct
40 Correct 822 ms 137916 KB Output is correct
41 Correct 17 ms 125784 KB Output is correct
42 Correct 349 ms 132816 KB Output is correct
43 Correct 492 ms 133864 KB Output is correct
44 Correct 793 ms 137932 KB Output is correct
45 Correct 798 ms 138116 KB Output is correct
46 Correct 594 ms 136416 KB Output is correct
47 Correct 43 ms 128080 KB Output is correct
48 Correct 308 ms 132660 KB Output is correct
49 Correct 539 ms 133684 KB Output is correct
50 Correct 814 ms 138032 KB Output is correct
51 Correct 1002 ms 137852 KB Output is correct
52 Correct 858 ms 138196 KB Output is correct
53 Correct 753 ms 137736 KB Output is correct
54 Correct 867 ms 137736 KB Output is correct
55 Correct 560 ms 137504 KB Output is correct
56 Correct 712 ms 137952 KB Output is correct
57 Correct 1150 ms 138016 KB Output is correct
58 Correct 1373 ms 138264 KB Output is correct
59 Correct 1294 ms 137792 KB Output is correct
60 Correct 1271 ms 137888 KB Output is correct
61 Correct 1404 ms 137756 KB Output is correct
62 Correct 1491 ms 137840 KB Output is correct
63 Correct 1492 ms 137920 KB Output is correct
64 Correct 1326 ms 138292 KB Output is correct
65 Correct 1364 ms 137928 KB Output is correct
66 Correct 384 ms 135124 KB Output is correct
67 Correct 604 ms 136140 KB Output is correct
68 Correct 780 ms 139212 KB Output is correct
69 Correct 724 ms 138452 KB Output is correct
70 Correct 624 ms 140492 KB Output is correct
71 Correct 755 ms 141004 KB Output is correct
72 Correct 856 ms 141032 KB Output is correct
73 Correct 965 ms 140904 KB Output is correct
74 Correct 145 ms 132944 KB Output is correct
75 Correct 216 ms 138476 KB Output is correct
76 Correct 873 ms 142032 KB Output is correct
77 Correct 837 ms 136400 KB Output is correct
78 Correct 840 ms 136644 KB Output is correct
79 Correct 1006 ms 140828 KB Output is correct
80 Correct 841 ms 136596 KB Output is correct
81 Correct 949 ms 140808 KB Output is correct
82 Correct 909 ms 136392 KB Output is correct
83 Correct 1344 ms 141436 KB Output is correct
84 Correct 873 ms 136940 KB Output is correct
85 Correct 1438 ms 141156 KB Output is correct
86 Correct 894 ms 136732 KB Output is correct
87 Correct 1462 ms 141032 KB Output is correct
88 Correct 907 ms 136588 KB Output is correct
89 Correct 1249 ms 142100 KB Output is correct