Submission #1106909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106909		Neco_arc	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	880 ms	36680 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define name "Sjeckanje"
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b)  for(int i = a; i <= b; ++i)
#define fid(i, a, b) for(int i = a; i >= b; --i)
#define maxn (int) (2e5 + 5)

using namespace std;

int n, q;
ll a[maxn];

struct IT {
    struct Node {
        ll f[2][2];
        Node() { memset(f, 0, sizeof f); }
    } st[4 * maxn];

    Node cb(const Node &x, const Node &y, int l, int r) {
        ll w = a[(l + r) >> 1];
        Node ans;

        fi(i, 0, 1) fi(j, 0, 1) fi(u, 0, 1) fi(v, 0, 1) {
            ll val = j ? w : -w; val = max(val, 0ll);
            ans.f[i][v] = max(ans.f[i][v], x.f[i][j] + y.f[u][v] + (j == u) * val);
        }

        return ans;
    }

    void update(int x, int id = 1, int l = 1, int r = n) {
        if(l > x || r < x) return;
        if(l == r) {
            st[id].f[0][1] = st[id].f[1][0] = -1e18;
            return;
        }

        int mid = (l + r) >> 1;
        update(x, _left), update(x, _right);

        st[id] = cb(st[id * 2], st[id * 2 + 1], l, r);
    }

    ll get(ll ans = 0) {
        fi(i, 0, 1) fi(j, 0, 1) ans = max(ans, st[1].f[i][j]);
        return ans;
    }

} St;


void solve() {

    cin >> n >> q;
    fi(i, 1, n) cin >> a[i];

    fi(i, 1, n - 1) a[i] = a[i] - a[i + 1];
    fi(i, 1, n) St.update(i);

    fi(i, 1, q) {
        int l, r; ll val; cin >> l >> r >> val;
        a[l - 1] -= val, a[r] += val;

        St.update(l), St.update(r);
        cout << St.get() << '\n';
    }


}


int main() {

    ios_base::sync_with_stdio();
    cin.tie(), cout.tie();

    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    solve();

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55