oj.uz

Submission #922275

# Submission time Handle Problem Language Result Execution time Memory
922275 2024-02-05T10:54:40 Z Github Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 943 ms 49320 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <stack>
#include <set>
#include <sstream>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
const ll INF = 1e9;

struct node{
    ll corner[2];
    ll dp[2][2];
};

node null = {0, 0, 0, 0, 0, 0};
class SegmentTree{
private:
    int n;
    vector<node> st;
public:
    SegmentTree(int m){
        n = m;
        st.resize(4*n, null);
    }

    node combine(node a, node b){
        node p = null;
        p.corner[0] = a.corner[0];
        p.corner[1] = b.corner[1];
        for (int l = 0; l < 2; l++){
            for (int s = 0; s < 2; s++){
                for (int t= 0; t < 2; t++){
                    for (int r = 0; r < 2; r++){
                        if (s && t){
                            if (a.corner[1]*b.corner[0] > 0){
                                p.dp[l][r] = max(p.dp[l][r], a.dp[l][s]+b.dp[t][r]);
                            }
                        }else{
                            p.dp[l][r] = max(p.dp[l][r], a.dp[l][s]+b.dp[t][r]);
                        }
                    }
                }
            }
        }
        return p;
    }

    void update(int p, int L, int R, int idx, ll x){
        if (L == R){
            st[p].corner[0] += x;
            st[p].corner[1] += x;
            st[p].dp[1][1] = abs(st[p].corner[0]);
            return;
        }
        int m = (L+R)/2;
        if (idx <= m){
            update(2*p, L, m,  idx, x);
        }else{
            update(2*p+1, m+1, R , idx, x);
        }
        st[p] = combine(st[2*p], st[2*p+1]);
    }

    node query(int p, int L, int R, int l, int r){
        if (l <= L && R <= r){
            return st[p];
        }
        if (R < l || L > r){
            return null;
        }
        int m = (L+R)/2;
        return combine(query(2*p, L, m, l, r), query(2*p+1, m+1, R, l, r));
    }
};

int main(){
    speedup
    int n, q; cin >> n >> q;
    SegmentTree T(n-1);
    ll prev = 0, cur;
    vector<ll> a(n);
    for (int i = 0; i < n; i++){
        cin >> cur;
        a[i] = cur;
        if (i){
            T.update(1, 0, n-2, i-1, cur-prev);
        }
        prev = cur;
    }
    for (int i = 0; i < q; i++){
        int l, r; cin >> l >> r; ll x; cin >> x;
        l--,r--;
        if (l >= 1){
            T.update(1, 0, n-2, l-1, x);
        }
        if (r < n-1) {
            T.update(1, 0, n - 2, r, -x);
        }
        cout << T.query(1, 0, n-2, 0, n-2).dp[1][1] << endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 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 10 ms 1116 KB Output is correct
8 Correct 9 ms 1116 KB Output is correct
9 Correct 10 ms 980 KB Output is correct
10 Correct 10 ms 1112 KB Output is correct
11 Correct 10 ms 1116 KB Output is correct
12 Correct 9 ms 1172 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 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 10 ms 1116 KB Output is correct
8 Correct 9 ms 1116 KB Output is correct
9 Correct 10 ms 980 KB Output is correct
10 Correct 10 ms 1112 KB Output is correct
11 Correct 10 ms 1116 KB Output is correct
12 Correct 9 ms 1172 KB Output is correct
13 Correct 899 ms 48836 KB Output is correct
14 Correct 857 ms 48704 KB Output is correct
15 Correct 902 ms 48672 KB Output is correct
16 Correct 892 ms 48588 KB Output is correct
17 Correct 943 ms 48480 KB Output is correct
18 Correct 918 ms 49320 KB Output is correct