oj.uz

Submission #1118238

# Submission time Handle Problem Language Result Execution time Memory
1118238 2024-11-25T06:41:19 Z Thunnus Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 729 ms 50760 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

struct SegTree{
    struct Node{
        int dp[2][2] = {};
        int borders[2] = {};
        Node() {}
        Node(int val) {
			dp[0][0] = dp[0][1] = dp[1][0] = 0;
            dp[1][1] = abs(val);
            borders[0] = borders[1] = val;
        }

        inline void node_update(int val){
            borders[0] += val, borders[1] += val;
            dp[1][1] = abs(borders[0]);
            return;
        }
    };
    vector<Node> st;
    SegTree(int n) : st(4 * n) {}

    inline Node combine(Node &a, Node &b){
        Node c;
        c.borders[0] = a.borders[0], c.borders[1] = b.borders[1];
        // [	 ][	 ]
		// l	 mo	 r
		// m and o same -> taken segments are combined
        for(int l = 0; l < 2; l++){
            for(int r = 0; r < 2; r++){
                for(int m = 0; m < 2; m++){
                    for(int o = 0; o < 2; o++){
                        if(m && o){
                            if((a.borders[1] < 0) == (b.borders[0] < 0)){
                                c.dp[l][r] = max(c.dp[l][r], a.dp[l][m] + b.dp[o][r]);
                            }
                        }
                        else{
                            c.dp[l][r] = max(c.dp[l][r], a.dp[l][m] + b.dp[o][r]);
                        }
                    }
                }
            }
        }
        return c;
    }

    inline void update(int pos, int val, int v, int tl, int tr){
        if(tl == tr){
            st[v].node_update(val);
            return;
        }
        int mid = (tl + tr) / 2;
        if(pos <= mid){
            update(pos, val, 2 * v, tl, mid);
        }
        else{
            update(pos, val, 2 * v + 1, mid + 1, tr);
        }
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        return;
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q;
    cin >> n >> q;
    vi a(n), diff(n - 1);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(i){
            diff[i - 1] = a[i] - a[i - 1];
        }
    }

    SegTree st(n - 1);
    for(int i = 0; i < n - 1; i++){
        st.update(i + 1, diff[i], 1, 1, n - 1);
    }
    while(q--){
        int l, r, x;
        cin >> l >> r >> x;
        if(l - 1 >= 1) st.update(l - 1, x, 1, 1, n - 1);
        if(r <= n - 1) st.update(r, -x, 1, 1, n - 1);
        cout << st.st[1].dp[1][1] << "\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 6 ms 1116 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 9 ms 1116 KB Output is correct
10 Correct 6 ms 1176 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 7 ms 1116 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 6 ms 1116 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 9 ms 1116 KB Output is correct
10 Correct 6 ms 1176 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 7 ms 1116 KB Output is correct
13 Correct 568 ms 50248 KB Output is correct
14 Correct 627 ms 50260 KB Output is correct
15 Correct 700 ms 50264 KB Output is correct
16 Correct 729 ms 49992 KB Output is correct
17 Correct 698 ms 50108 KB Output is correct
18 Correct 603 ms 50760 KB Output is correct