oj.uz

Submission #847067

# Submission time Handle Problem Language Result Execution time Memory
847067 2023-09-09T05:47:34 Z eltu0815 Ants and Sugar (JOI22_sugar) C++14
100 / 100
 1542 ms 142064 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]));
        
        // 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 has a negative or zero contribution
        // so when we merge with the set whose |S| is 0, it's always optimal to contribute -(lazy updates of lz1),
        // so that it can be combined with l[i][1] and r[1][j].
        
        // 한국어로 다시 쓰자면, 아무런 개미가 선택되지 않은 셋은 항상 음수 또는 0의 기여도를 가지는데,
        // 이들이 양옆에 있는 노드의 1과 결합하면 양수의 기여도를 가지게 할 수 있음
        // 따라서 아무런 개미가 선택되지 않은 노드는 그 노드의 x 전체를 1로 만들어 merge하는 경우까지 추가로 고려해야 하며,
        // 그 노드 x 전체를 1로 만들면 기여도는 그 구간에서 발생한 lz1 업데이트의 총합임
        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:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update1(int, int, int, int, ll, int)':
sugar.cpp:92:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update2(int, int, int, int, ll, int)':
sugar.cpp:106:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update3(int, int, int, ll, int)':
sugar.cpp:119:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |     int mid = str + ed >> 1;
      |               ~~~~^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 125788 KB Output is correct
2 Correct 17 ms 125620 KB Output is correct
3 Correct 18 ms 125784 KB Output is correct
4 Correct 18 ms 125748 KB Output is correct
5 Correct 18 ms 125800 KB Output is correct
6 Correct 19 ms 125788 KB Output is correct
7 Correct 20 ms 125788 KB Output is correct
8 Correct 18 ms 125788 KB Output is correct
9 Correct 18 ms 125668 KB Output is correct
10 Correct 22 ms 126032 KB Output is correct
11 Correct 21 ms 125716 KB Output is correct
12 Correct 20 ms 125836 KB Output is correct
13 Correct 20 ms 125840 KB Output is correct
14 Correct 19 ms 125788 KB Output is correct
15 Correct 21 ms 125788 KB Output is correct
16 Correct 20 ms 125788 KB Output is correct
17 Correct 21 ms 125740 KB Output is correct
18 Correct 20 ms 125676 KB Output is correct
19 Correct 19 ms 125788 KB Output is correct
20 Correct 20 ms 125668 KB Output is correct
21 Correct 21 ms 125784 KB Output is correct
22 Correct 20 ms 125788 KB Output is correct
23 Correct 23 ms 125824 KB Output is correct
24 Correct 20 ms 125788 KB Output is correct
25 Correct 22 ms 125668 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 125672 KB Output is correct
2 Correct 17 ms 125788 KB Output is correct
3 Correct 17 ms 125784 KB Output is correct
4 Correct 599 ms 137932 KB Output is correct
5 Correct 384 ms 134416 KB Output is correct
6 Correct 759 ms 139224 KB Output is correct
7 Correct 392 ms 134608 KB Output is correct
8 Correct 823 ms 140516 KB Output is correct
9 Correct 824 ms 141448 KB Output is correct
10 Correct 861 ms 140808 KB Output is correct
11 Correct 827 ms 141400 KB Output is correct
12 Correct 362 ms 132984 KB Output is correct
13 Correct 490 ms 133728 KB Output is correct
14 Correct 793 ms 137868 KB Output is correct
15 Correct 793 ms 137932 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 125788 KB Output is correct
2 Correct 352 ms 132576 KB Output is correct
3 Correct 499 ms 133840 KB Output is correct
4 Correct 810 ms 137876 KB Output is correct
5 Correct 806 ms 138188 KB Output is correct
6 Correct 588 ms 136388 KB Output is correct
7 Correct 43 ms 128168 KB Output is correct
8 Correct 299 ms 132356 KB Output is correct
9 Correct 584 ms 133516 KB Output is correct
10 Correct 864 ms 137828 KB Output is correct
11 Correct 993 ms 137680 KB Output is correct
12 Correct 897 ms 138096 KB Output is correct
13 Correct 775 ms 137676 KB Output is correct
14 Correct 888 ms 137696 KB Output is correct
15 Correct 552 ms 137680 KB Output is correct
16 Correct 751 ms 138064 KB Output is correct
17 Correct 1197 ms 137856 KB Output is correct
18 Correct 1397 ms 138340 KB Output is correct
19 Correct 1317 ms 137956 KB Output is correct
20 Correct 1348 ms 138116 KB Output is correct
21 Correct 1416 ms 138304 KB Output is correct
22 Correct 1542 ms 138004 KB Output is correct
23 Correct 1512 ms 138064 KB Output is correct
24 Correct 1299 ms 137788 KB Output is correct
25 Correct 1458 ms 138168 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 125788 KB Output is correct
2 Correct 17 ms 125620 KB Output is correct
3 Correct 18 ms 125784 KB Output is correct
4 Correct 18 ms 125748 KB Output is correct
5 Correct 18 ms 125800 KB Output is correct
6 Correct 19 ms 125788 KB Output is correct
7 Correct 20 ms 125788 KB Output is correct
8 Correct 18 ms 125788 KB Output is correct
9 Correct 18 ms 125668 KB Output is correct
10 Correct 22 ms 126032 KB Output is correct
11 Correct 21 ms 125716 KB Output is correct
12 Correct 20 ms 125836 KB Output is correct
13 Correct 20 ms 125840 KB Output is correct
14 Correct 19 ms 125788 KB Output is correct
15 Correct 21 ms 125788 KB Output is correct
16 Correct 20 ms 125788 KB Output is correct
17 Correct 21 ms 125740 KB Output is correct
18 Correct 20 ms 125676 KB Output is correct
19 Correct 19 ms 125788 KB Output is correct
20 Correct 20 ms 125668 KB Output is correct
21 Correct 21 ms 125784 KB Output is correct
22 Correct 20 ms 125788 KB Output is correct
23 Correct 23 ms 125824 KB Output is correct
24 Correct 20 ms 125788 KB Output is correct
25 Correct 22 ms 125668 KB Output is correct
26 Correct 19 ms 125672 KB Output is correct
27 Correct 17 ms 125788 KB Output is correct
28 Correct 17 ms 125784 KB Output is correct
29 Correct 599 ms 137932 KB Output is correct
30 Correct 384 ms 134416 KB Output is correct
31 Correct 759 ms 139224 KB Output is correct
32 Correct 392 ms 134608 KB Output is correct
33 Correct 823 ms 140516 KB Output is correct
34 Correct 824 ms 141448 KB Output is correct
35 Correct 861 ms 140808 KB Output is correct
36 Correct 827 ms 141400 KB Output is correct
37 Correct 362 ms 132984 KB Output is correct
38 Correct 490 ms 133728 KB Output is correct
39 Correct 793 ms 137868 KB Output is correct
40 Correct 793 ms 137932 KB Output is correct
41 Correct 17 ms 125788 KB Output is correct
42 Correct 352 ms 132576 KB Output is correct
43 Correct 499 ms 133840 KB Output is correct
44 Correct 810 ms 137876 KB Output is correct
45 Correct 806 ms 138188 KB Output is correct
46 Correct 588 ms 136388 KB Output is correct
47 Correct 43 ms 128168 KB Output is correct
48 Correct 299 ms 132356 KB Output is correct
49 Correct 584 ms 133516 KB Output is correct
50 Correct 864 ms 137828 KB Output is correct
51 Correct 993 ms 137680 KB Output is correct
52 Correct 897 ms 138096 KB Output is correct
53 Correct 775 ms 137676 KB Output is correct
54 Correct 888 ms 137696 KB Output is correct
55 Correct 552 ms 137680 KB Output is correct
56 Correct 751 ms 138064 KB Output is correct
57 Correct 1197 ms 137856 KB Output is correct
58 Correct 1397 ms 138340 KB Output is correct
59 Correct 1317 ms 137956 KB Output is correct
60 Correct 1348 ms 138116 KB Output is correct
61 Correct 1416 ms 138304 KB Output is correct
62 Correct 1542 ms 138004 KB Output is correct
63 Correct 1512 ms 138064 KB Output is correct
64 Correct 1299 ms 137788 KB Output is correct
65 Correct 1458 ms 138168 KB Output is correct
66 Correct 395 ms 135064 KB Output is correct
67 Correct 567 ms 136344 KB Output is correct
68 Correct 780 ms 139176 KB Output is correct
69 Correct 734 ms 138228 KB Output is correct
70 Correct 625 ms 140756 KB Output is correct
71 Correct 752 ms 140780 KB Output is correct
72 Correct 863 ms 140868 KB Output is correct
73 Correct 959 ms 141204 KB Output is correct
74 Correct 141 ms 132948 KB Output is correct
75 Correct 208 ms 138320 KB Output is correct
76 Correct 866 ms 142064 KB Output is correct
77 Correct 848 ms 136412 KB Output is correct
78 Correct 870 ms 136416 KB Output is correct
79 Correct 1002 ms 141008 KB Output is correct
80 Correct 885 ms 137188 KB Output is correct
81 Correct 937 ms 141204 KB Output is correct
82 Correct 855 ms 136584 KB Output is correct
83 Correct 1335 ms 141380 KB Output is correct
84 Correct 857 ms 136920 KB Output is correct
85 Correct 1426 ms 141500 KB Output is correct
86 Correct 873 ms 136612 KB Output is correct
87 Correct 1444 ms 141268 KB Output is correct
88 Correct 869 ms 136636 KB Output is correct
89 Correct 1241 ms 141944 KB Output is correct