oj.uz

Submission #395093

# Submission time Handle Problem Language Result Execution time Memory
395093 2021-04-27T18:19:34 Z rocks03 Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 4296 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int N, Q;
vector<ll> a;

void update(int l, int r, ll k){
    rep(i, l, r + 1) a[i] += k;
}

class SegmentTree{
    public:
    vector<int> st;
    void build(int n){
        st = vector<int>(4 * n, 0);
    }
    void merge(int i){
        int cl = 2 * i + 1, cr = 2 * i + 2;
        st[i] = max(st[cl], st[cr]);
    }
    void set(int i, int l, int r, int p, int k){
        if(l == r) st[i] = max(st[i], k);
        else{
            int m = (l + r) / 2;
            if(p <= m)
                set(2 * i + 1, l, m, p, k);
            else
                set(2 * i + 2, m + 1, r, p, k);
            merge(i);
        }
    }
    int query(int i, int l, int r, int ql, int qr){
        if(ql <= l && r <= qr){
            return st[i];
        }
        if(qr < l || ql > r){
            return 0;
        }
        int m = (l + r) / 2;
        int ans1 = query(2 * i + 1, l, m, ql, qr);
        int ans2 = query(2 * i + 2, m + 1, r, ql, qr);
        return max(ans1, ans2);
    }
} st, st1, st2;

ll get(){
    ll dp1 = -a[0];
    ll dp2 = +a[0];
    ll ans = 0;
    rep(i, 1, N){
        ll old_ans = ans;
        ans = max({ans, a[i] + dp1, dp2 - a[i]});
        dp1 = max(dp1, old_ans - a[i]);
        dp2 = max(dp2, old_ans + a[i]);
    }
    return ans;
}

void solve(){
    cin >> N >> Q;
    a = vector<ll>(N);
    rep(i, 0, N) cin >> a[i];
    rep(q, 0, Q){
        int l, r; ll k;
        cin >> l >> r >> k;
        --l, --r;
        update(l, r, k);
        cout << get() << "\n";
    }
}
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 29 ms 456 KB Output is correct
8 Correct 28 ms 464 KB Output is correct
9 Correct 28 ms 448 KB Output is correct
10 Correct 28 ms 456 KB Output is correct
11 Correct 29 ms 448 KB Output is correct
12 Correct 28 ms 452 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 29 ms 456 KB Output is correct
8 Correct 28 ms 464 KB Output is correct
9 Correct 28 ms 448 KB Output is correct
10 Correct 28 ms 456 KB Output is correct
11 Correct 29 ms 448 KB Output is correct
12 Correct 28 ms 452 KB Output is correct
13 Execution timed out 2035 ms 4296 KB Time limit exceeded
14 Halted 0 ms 0 KB -