oj.uz

Submission #639455

# Submission time Handle Problem Language Result Execution time Memory
639455 2022-09-10T01:38:25 Z vbee Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1217 ms 47688 KB 
#include <bits/stdc++.h>
#define TASK ""
#define ll long long
#define fi first
#define se second
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define ii pair<int, int>
#define vi vector<int>

using namespace std;

const int oo = 1e9 + 7;
const int mod = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int N = 2e5 + 7;

bool maximize(ll &a, ll b){
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
struct Node{
    ll border[2] = {};
    ll value[2][2] = {};
    Node(){}
    Node (ll val){
        border[0] = border[1] = val;
        value[0][0] = 0;
        value[0][1] = value[1][0] = -loo;
        value[1][1] = abs(val);
    }

    Node combine(const Node &other) const {
        Node ret;
        ret.border[0] = border[0];
        ret.border[1] = other.border[1];
        for (int l = 0; l < 2; l++){
            for (int m = 0; m < 2; m++){
                for (int o = 0; o < 2; o++){
                    for (int r = 0; r < 2; r++){
                        if (o && m){
                            if ((border[1] < 0) == (other.border[0] < 0)){
                                maximize(ret.value[l][r], value[l][m] + other.value[o][r]);
                            }
                        }
                        else maximize(ret.value[l][r], value[l][m] + other.value[o][r]);
                    }
                }
            }
        }
        return ret;
    }

};

struct ST{
    vector<Node> t;
    void init(int n){
        t.resize(n * 4 + 7);
    }
    void update(int v, int lt, int rt, int pos, ll value){
        if (lt == rt){
            t[v].border[0] += value;
            t[v].border[1] += value;
            t[v].value[1][1] = abs(t[v].border[0]);
            return;
        }
        int middle = (rt + lt) / 2;
        if (pos <= middle) update(v * 2, lt, middle, pos, value);
        else update(v * 2 + 1, middle + 1, rt, pos, value);
        t[v] = t[v * 2].combine(t[v * 2 + 1]);
    }
    Node getmax(int v, int lt, int rt, int l, int r){
        if (l > r) return Node(0);
        if (lt == l && rt == r) return t[v];
        int middle = (rt + lt) / 2;
        Node temp = getmax(v * 2, lt, middle, l, min(middle, r));
        return temp.combine(getmax(v * 2 + 1, middle + 1, rt, max(middle + 1, l), r));
    }
};

ll n, q;

int main(){
    ios_base::sync_with_stdio(0); cin.tie();
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdout);
    cin >> n >> q;
    ST seg;
    seg.init(n - 1);
    int pre = 0;
    cin >> pre;
    for (int i = 1; i < n; i++){
        int x; cin >> x;
        seg.update(1, 1, n - 1, i, x - pre);
        pre = x;
    }
    while (q--){
        int l, r, x; cin >> l >> r >> x;
        if (l > 1) seg.update(1, 1, n - 1, l - 1, x);
        if (r < n) seg.update(1, 1, n - 1, r, -x);
        cout << seg.getmax(1, 1, n - 1, 1, n - 1).value[1][1] << "\n";
    }
    return 0;
}

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 328 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 2 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 328 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 12 ms 1016 KB Output is correct
8 Correct 14 ms 988 KB Output is correct
9 Correct 12 ms 980 KB Output is correct
10 Correct 12 ms 980 KB Output is correct
11 Correct 13 ms 980 KB Output is correct
12 Correct 13 ms 980 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 328 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 12 ms 1016 KB Output is correct
8 Correct 14 ms 988 KB Output is correct
9 Correct 12 ms 980 KB Output is correct
10 Correct 12 ms 980 KB Output is correct
11 Correct 13 ms 980 KB Output is correct
12 Correct 13 ms 980 KB Output is correct
13 Correct 1178 ms 47036 KB Output is correct
14 Correct 1158 ms 47120 KB Output is correct
15 Correct 1187 ms 47128 KB Output is correct
16 Correct 1217 ms 46960 KB Output is correct
17 Correct 1208 ms 46836 KB Output is correct
18 Correct 1148 ms 47688 KB Output is correct