oj.uz

Submission #937708

# Submission time Handle Problem Language Result Execution time Memory
937708 2024-03-04T11:42:44 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 494 ms 30648 KB 
/* In the name of God */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 2e5 + 5;

ll seg[MAXN << 2][2][2], a[MAXN], dif[MAXN];
#define lc id << 1
#define rc id << 1 | 1

bool same(int i, int j){
    if (dif[i] < 0 && dif[j] > 0) return 0;
    if (dif[i] > 0 && dif[j] < 0) return 0;
    return 1;
}

void build(int id, int l, int r){
    if (r - l == 1){
        seg[id][1][1] = abs(dif[l]);
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid, r);
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            for (int ii = 0; ii < 2; ii++){
                for (int jj = 0; jj < 2; jj++){
                    if (ii == jj && ii == 1){
                        if (same(mid - 1, mid)) seg[id][i][j] = max(seg[id][i][j], seg[lc][i][ii] + seg[rc][jj][j]);
                    } else {
                        seg[id][i][j] = max(seg[id][i][j], seg[lc][i][ii] + seg[rc][jj][j]);
                    }
                }
            }
        }
    }
}

void upd(int id, int l, int r, int ql, int qr, int delta){
    if (ql >= r || qr <= l) return;
    if (l >= ql && r <= qr){
        dif[l] += delta;
        seg[id][1][1] = abs(dif[l]);
        return;
    }
    int mid = l + r >> 1;
    upd(lc, l, mid, ql, qr, delta);
    upd(rc, mid, r, ql, qr, delta);
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            seg[id][i][j] = 0;
            for (int ii = 0; ii < 2; ii++){
                for (int jj = 0; jj < 2; jj++){
                    if (ii == jj && ii == 1){
                        if (same(mid - 1, mid)) seg[id][i][j] = max(seg[id][i][j], seg[lc][i][ii] + seg[rc][jj][j]);
                    } else {
                        seg[id][i][j] = max(seg[id][i][j], seg[lc][i][ii] + seg[rc][jj][j]);
                    }
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++){
        dif[i] = a[i] - a[i + 1];
    }
    build(1, 1, n);
    while (q--){
        int l, r, x;
        cin >> l >> r >> x;
        if (l != 1) upd(1, 1, n, l - 1, l, -x);
        if (r != n) upd(1, 1, n, r, r + 1, +x);
        ll ans = 0;
        for (int i : {0, 1}) for (int j : {0, 1}) ans = max(ans, seg[1][i][j]);
        cout << ans << endl;
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:73:17: 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 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct
8 Correct 5 ms 4444 KB Output is correct
9 Correct 5 ms 4444 KB Output is correct
10 Correct 5 ms 4440 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 5 ms 4632 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct
8 Correct 5 ms 4444 KB Output is correct
9 Correct 5 ms 4444 KB Output is correct
10 Correct 5 ms 4440 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 5 ms 4632 KB Output is correct
13 Correct 493 ms 29844 KB Output is correct
14 Correct 490 ms 30144 KB Output is correct
15 Correct 494 ms 30152 KB Output is correct
16 Correct 490 ms 30036 KB Output is correct
17 Correct 476 ms 30124 KB Output is correct
18 Correct 437 ms 30648 KB Output is correct