oj.uz

Submission #1106909

# Submission time Handle Problem Language Result Execution time Memory
1106909 2024-10-31T09:06:42 Z Neco_arc Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 880 ms 36680 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25424 KB Output is correct
2 Correct 4 ms 25424 KB Output is correct
3 Correct 5 ms 25692 KB Output is correct
4 Correct 4 ms 25424 KB Output is correct
5 Correct 4 ms 25424 KB Output is correct
6 Correct 4 ms 25424 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25424 KB Output is correct
2 Correct 4 ms 25424 KB Output is correct
3 Correct 5 ms 25692 KB Output is correct
4 Correct 4 ms 25424 KB Output is correct
5 Correct 4 ms 25424 KB Output is correct
6 Correct 4 ms 25424 KB Output is correct
7 Correct 13 ms 25624 KB Output is correct
8 Correct 13 ms 25436 KB Output is correct
9 Correct 13 ms 25424 KB Output is correct
10 Correct 13 ms 25628 KB Output is correct
11 Correct 13 ms 25616 KB Output is correct
12 Correct 13 ms 25596 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25424 KB Output is correct
2 Correct 4 ms 25424 KB Output is correct
3 Correct 5 ms 25692 KB Output is correct
4 Correct 4 ms 25424 KB Output is correct
5 Correct 4 ms 25424 KB Output is correct
6 Correct 4 ms 25424 KB Output is correct
7 Correct 13 ms 25624 KB Output is correct
8 Correct 13 ms 25436 KB Output is correct
9 Correct 13 ms 25424 KB Output is correct
10 Correct 13 ms 25628 KB Output is correct
11 Correct 13 ms 25616 KB Output is correct
12 Correct 13 ms 25596 KB Output is correct
13 Correct 825 ms 36184 KB Output is correct
14 Correct 872 ms 36068 KB Output is correct
15 Correct 863 ms 36096 KB Output is correct
16 Correct 873 ms 35872 KB Output is correct
17 Correct 812 ms 36004 KB Output is correct
18 Correct 880 ms 36680 KB Output is correct