oj.uz

Submission #1011945

# Submission time Handle Problem Language Result Execution time Memory
1011945 2024-07-01T11:34:37 Z fryingduc Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 229 ms 50768 KB 
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)          
#endif

#define int long long


const int maxn = 2e5+5;
int n, a[maxn], q, d[maxn];

namespace sub12{
    const int N = 3005;
    int f[N][2];
    void compute(){
        d[0] = d[n] = 0;
        for(int i = 1; i <= n; ++i){
            if(d[i] * d[i - 1] < 0){
                f[i][0] = max(f[i - 1][1], f[i - 1][0]);
                f[i][1] = max(f[i - 1][0], f[i - 1][1] - abs(d[i - 1])) + abs(d[i]);
            }
            else{
                f[i][0] = max(f[i - 1][0], f[i - 1][1]);
                f[i][1] = max(f[i - 1][0], f[i - 1][1]) + abs(d[i]);
            }
//            debug(i, f[i][0], f[i][1]);
        }
    }
    void solve(){
        while(q--){
            int l, r, x; cin >> l >> r >> x;
            d[l - 1] -= x;
            d[r] += x;
            compute();
            cout << max(f[n][0], f[n][1]) << '\n';
        }
    }
}
namespace sub3{
    struct Node{
        int f[4], head, tail;
        Node() {
            f[0] = f[1] = f[2] = f[3];
        }
        Node (int x, int y, int z, int t, int head, int tail) : head(head), tail(tail) {
            f[0] = x, f[1] = y, f[2] = z, f[3] = t;
        }
        friend Node operator + (const Node &a, const Node &b){
            Node res;
            if(a.tail * b.head < 0){
                res.f[0] = max(a.f[2] + b.f[0], a.f[0] + b.f[1]);
                res.f[1] = max(a.f[1] + b.f[1], a.f[3] + b.f[0]);
                res.f[2] = max(a.f[0] + b.f[3], a.f[2] + b.f[2]);
                res.f[3] = max(a.f[1] + b.f[3], a.f[3] + b.f[2]);
            }   
            else{
                res.f[0] = a.f[0] + b.f[0];
                res.f[1] = a.f[1] + b.f[0];
                res.f[2] = a.f[0] + b.f[2];
                res.f[3] = a.f[1] + b.f[2];
            }
            res.head = a.head;
            res.tail = b.tail;
            return res;
        }
    };
    struct SegmentTree{
        int n;
        vector<Node> tree;
        void init(int sz){
            n = sz;
            tree.resize(n * 4 + 6);
        }
        void build(int ind, int l, int r){
            if(l == r){
                tree[ind] = Node(abs(d[l]), 0, 0, 0, d[l], d[l]);
                return;
            }
            int mid = (l + r) / 2;
            build(ind * 2, l, mid);
            build(ind * 2 + 1, mid + 1, r);
            tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
        }
        void update(int ind, int l, int r, int pos, int val){
            if(l == r){
                d[l] += val;
                tree[ind] = Node(abs(d[l]), 0, 0, 0, d[l], d[l]);
                return;
            }
            int mid = (l + r) / 2;
            if(l <= pos and pos <= mid) update(ind * 2, l, mid, pos, val);
            else update(ind * 2 + 1, mid + 1, r, pos, val);
            tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
        }
        void update(int pos, int val){
            update(1, 1, n, pos, val);
        }
        int get(){
            return tree[1].f[0];
        }
    } st;
    void solve(){
        st.init(n);
        st.build(1, 1, n);
        while(q--){
            int l, r, x; cin >> l >> r >> x;
            if(l > 1) st.update(l - 1, -x);
            if(r < n) st.update(r, x);
            cout << st.get() << '\n';
        }
    }
}
void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for(int i = 1; i < n; ++i){
        d[i] = (a[i] - a[i + 1]);
    }
//    if(n <= 3000){
//        sub12::solve();
//        return;
//    }
    sub3::solve();
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
}

Compilation message

Main.cpp: In constructor 'sub3::Node::Node()':
Main.cpp:46:37: warning: '*<unknown>.sub3::Node::f[3]' is used uninitialized in this function [-Wuninitialized]
   46 |             f[0] = f[1] = f[2] = f[3];
      |                                  ~~~^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 3 ms 1204 KB Output is correct
9 Correct 3 ms 1112 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 2 ms 984 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 3 ms 1204 KB Output is correct
9 Correct 3 ms 1112 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 2 ms 984 KB Output is correct
13 Correct 199 ms 50288 KB Output is correct
14 Correct 225 ms 50260 KB Output is correct
15 Correct 219 ms 50064 KB Output is correct
16 Correct 217 ms 50012 KB Output is correct
17 Correct 229 ms 50256 KB Output is correct
18 Correct 201 ms 50768 KB Output is correct