oj.uz

Submission #794996

# Submission time Handle Problem Language Result Execution time Memory
794996 2023-07-27T05:00:08 Z hafo Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 521 ms 23164 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, q, l, r, x, d[maxn];
ll a[maxn];

struct ST {
    struct node {
        ll sum[2][2];
    };

    node st[4 * maxn];

    void merge(int id, int l, int r) {
        int mid = l + r >> 1, id1 = (id << 1), id2 = (id << 1 | 1);

        bool ex = 0;
        if((d[mid] < 0 && d[mid + 1] > 0) || (d[mid] > 0 && d[mid + 1] < 0)) ex = 1;
        memset(st[id].sum, 0, sizeof st[id].sum);
        for(int a = 0; a < 2; a++) {
            for(int b = 0; b < 2; b++) {
                for(int c = 0; c < 2; c++) {
                    for(int d = 0; d < 2; d++) {
                        if(ex == 1 && b != c) continue;
                        maxi(st[id].sum[a][d], st[id1].sum[a][b] + st[id2].sum[c][d]); 
                    }
                }
            }
        }
    }

    void build(int id, int l, int r) {
        if(l == r) {
            st[id].sum[0][1] = abs(d[l]);
            st[id].sum[0][0] = 0;
            st[id].sum[1][0] = 0;
            st[id].sum[1][1] = 0;
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        merge(id, l, r);
    }

    void update(int id, int l, int r, int pos) {
        if(pos < l || pos > r) return;
        if(l == r) {
            st[id].sum[0][1] = abs(d[l]);
            st[id].sum[0][0] = 0;
            st[id].sum[1][0] = 0;
            st[id].sum[1][1] = 0;
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, pos);
        update(id << 1 | 1, mid + 1, r, pos);
        merge(id, l, r);
    }

} st;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++) d[i] = (i == n ? 0:a[i] - a[i + 1]);

    st.build(1, 1, n);
    while(q--) {
        cin>>l>>r>>x;
        if(l - 1 >= 1) {
            d[l - 1] -= x;
            st.update(1, 1, n, l - 1);
        } 
        if(r != n) {
            d[r] += x;
            st.update(1, 1, n, r);
        }
        
        ll ans = 0;
        for(int i = 0; i < 2; i++) 
            for(int j = 0; j < 2; j++) maxi(ans, st.st[1].sum[i][j]);
        cout<<ans<<"\n";
    }
    return 0;
}

Compilation message

Main.cpp: In member function 'void ST::merge(int, int, int)':
Main.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = l + r >> 1, id1 = (id << 1), id2 = (id << 1 | 1);
      |                   ~~^~~
Main.cpp: In member function 'void ST::build(int, int, int)':
Main.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void ST::update(int, int, int, int)':
Main.cpp:73:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 5 ms 684 KB Output is correct
10 Correct 5 ms 684 KB Output is correct
11 Correct 5 ms 684 KB Output is correct
12 Correct 4 ms 744 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 5 ms 684 KB Output is correct
10 Correct 5 ms 684 KB Output is correct
11 Correct 5 ms 684 KB Output is correct
12 Correct 4 ms 744 KB Output is correct
13 Correct 491 ms 22992 KB Output is correct
14 Correct 499 ms 23088 KB Output is correct
15 Correct 521 ms 23076 KB Output is correct
16 Correct 507 ms 23048 KB Output is correct
17 Correct 469 ms 22944 KB Output is correct
18 Correct 403 ms 23164 KB Output is correct