oj.uz

Submission #1044641

# Submission time Handle Problem Language Result Execution time Memory
1044641 2024-08-05T11:58:28 Z underwaterkillerwhale Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 578 ms 50772 KB 
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const ll BASE = 137;

int n, Q;
int a[N];
struct Query {
    int l, r, X;
}qr[N];

struct Segment_Tree {
    struct Node {
        ll f[2][2], ps, ss;
    };
    int m;
    Node st[N << 2];

    void init (int n) {
        m = n;
        rep (i, 1, n << 2) st[i].f[0][1] = st[i].f[1][0] = -INF, st[i].f[1][1] = st[i].f[0][0] = 0;
    }

    Node mer (Node lf, Node rt) {
        Node cur;
        cur.ps = lf.ps;
        cur.ss = rt.ss;
        rep (i, 0, 1)
        rep (t, 0, 1) {
            cur.f[i][t] = -INF;
            rep (j, 0, 1)
            rep (k, 0, 1) {
                if ((lf.ss < 0 && rt.ps > 0) || (lf.ss > 0 && rt.ps < 0)) {
                    if (j != k || (j == 0 && k == 0)) cur.f[i][t] = max(cur.f[i][t], lf.f[i][j] + rt.f[k][t]);
                }
                else {
                    cur.f[i][t] = max(cur.f[i][t], lf.f[i][j] + rt.f[k][t]);
                }
            }
        }
        return cur;
    }

    void update (int id, int l, int r, int pos, ll val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id].ps += val;
            st[id].ss += val;
            st[id].f[1][1] = abs(st[id].ps);
            return;
        }
        int mid = l + r >> 1;
        update (id << 1, l, mid, pos, val);
        update (id << 1 | 1, mid + 1, r, pos, val);
        st[id] = mer (st[id << 1], st[id << 1 | 1]);
    }
    void update (int pos, int val) {
        update (1, 1, m, pos, val);
    }
}ST;

void solution () {
    cin >> n >> Q;
    rep (i, 1, n) cin >> a[i];
    ST.init(n - 1);
    rep (i, 1, n - 1) ST.update (i, a[i + 1] - a[i]);
    rep (q, 1, Q) {
        cin >> qr[q].l >> qr[q].r >> qr[q].X;
        ST.update(qr[q].l - 1, qr[q].X);
        ST.update(qr[q].r, -qr[q].X);
        ll res = 0;
        rep (i, 0, 1)
        rep (j, 0, 1)
            res = max(res, ST.st[1].f[i][j]);
        cout << res<<"\n";
    }
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +2
4
1 2 3 4
2
0 3
2 1
*/

Compilation message

Main.cpp: In member function 'void Segment_Tree::update(int, int, int, int, long long int)':
Main.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 9 ms 4700 KB Output is correct
8 Correct 6 ms 4700 KB Output is correct
9 Correct 6 ms 4700 KB Output is correct
10 Correct 6 ms 4700 KB Output is correct
11 Correct 6 ms 4664 KB Output is correct
12 Correct 8 ms 4700 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 9 ms 4700 KB Output is correct
8 Correct 6 ms 4700 KB Output is correct
9 Correct 6 ms 4700 KB Output is correct
10 Correct 6 ms 4700 KB Output is correct
11 Correct 6 ms 4664 KB Output is correct
12 Correct 8 ms 4700 KB Output is correct
13 Correct 576 ms 50260 KB Output is correct
14 Correct 559 ms 50260 KB Output is correct
15 Correct 578 ms 50168 KB Output is correct
16 Correct 560 ms 50004 KB Output is correct
17 Correct 519 ms 50004 KB Output is correct
18 Correct 529 ms 50772 KB Output is correct