oj.uz

Submission #479164

# Submission time Handle Problem Language Result Execution time Memory
479164 2021-10-10T12:15:12 Z Karliver Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 340 ms 27988 KB 
    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e5 + 2;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
int n, q;

ll S[4 * N][2][2];
int a[N], b[N];
void merge(int t, int x, int y) {
    
    forn(i, 2) forn(j, 2) S[t][i][j] = max(S[x][i][0] + S[y][0][j], S[x][i][1] + S[y][1][j]);
}
void upd(int pos, int val, int p = 1, int l = 1, int r = n) {
    if(l == r) {
        forn(i, 2) forn(j, 2) S[p][i][j] = 0;
        if(val < 0)S[p][0][0] = -val;
        else S[p][1][1] = val;
        return;
    }
    int rm = (l + r) >> 1;

    if(pos <= rm)
        upd(pos, val, p << 1, l, rm);
    else upd(pos, val, p << 1 | 1, rm + 1, r);
    
    merge(p, p << 1, p << 1 | 1);
}

VV<ll> range_qur(int il, int ir, int p = 1, int l = 1, int  r = n) {
    if(r < il || l > ir) {
        VV<ll> f(2, V<ll>(2));
        return f;
    }
    if(il <= l && r <= ir) {
        VV<ll> f(2, V<ll>(2));
        forn(i, 2) forn(j, 2) f[i][j] = S[p][i][j];
        return f;
    }

    int rm = (l + r) >> 1;

    auto L = range_qur(il, ir, p << 1, l, rm);
    auto R = range_qur(il, ir, p << 1 | 1, rm + 1, r);

    VV<ll>f(2, V<ll>(2));
    forn(i, 2) forn(j, 2) f[i][j] = max(L[i][0] + R[0][j], L[i][1] + R[1][j]);
    return f;
}


void solve() {

    cin >> n >> q;
    

    for(int i = 1;i <= n;++i)
        cin >> b[i];

    --n;
    for(int i = n;i;--i) {
        a[i] = b[i + 1] - b[i];
        upd(i, a[i]);
    }


    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        /*
        if(t == 1) {
            
            a[l] = r;
            if(l >  1) {
                upd(l - 1, a[l] - a[l - 1]);
            }
            if(l > 0 && l <= n) {
                upd(l, a[l + 1] - a[l]);
            }
        }
        else {
            if(l == r) {
                cout << 0 << '\n';
                continue;
            }
            auto D = range_qur(l, r - 1);
            ll ret = 0;
            forn(i, 2) forn(j, 2) ckma(ret, D[i][j]);
            cout << ret << '\n';
        }
        */

        if(l > 1)
            upd(l - 1, (a[l - 1] += x));

        if(r <= n)
            upd(r, (a[r] -= x));

        cout << max({S[1][0][0], S[1][0][1], S[1][1][0], S[1][1][1]}) << '\n';


    }



}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 268 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 3 ms 712 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 3 ms 588 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 268 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 3 ms 712 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 340 ms 25304 KB Output is correct
14 Correct 335 ms 27404 KB Output is correct
15 Correct 315 ms 27412 KB Output is correct
16 Correct 326 ms 27220 KB Output is correct
17 Correct 294 ms 27248 KB Output is correct
18 Correct 319 ms 27988 KB Output is correct