제출 #1152558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152558		jmuzhen	Sjeckanje (COCI21_sjeckanje)	C++20	15 / 110	2095 ms	71496 KiB

Main

#include<bits/stdc++.h>
using namespace std;

/*
 * Grab subtask 1 first. we can just solve the problem Q times, O(N^2) each with some dp.
 * so like dp(i) is max value of [0..i].
 * so some prerequisite:
 * - we can find the value of a segment in O(logN) with segtree.
 * so at each element, from dp(i) to dp(i-1), we can just choose to keep i or not depending on whether it improves the answer.
 * so O(logN) transition and O(N) states.
 * then base case: dp(0) is just 0.
 * but wait, what is the transition exactly?
 * wait, let's redefine the dp into 2d.
 * dp(i, j) is the max value of [i..j].
 * then, the transition is simple. we can choose to split at any point along i..j or not split at all.
 * so dp(i,j) is max(value(i,j), // ie. don't split
 *                  dp(i,k)+dp(k,j) for all i<=k<=j)
 *   then base case is
 *   if i == j then it's 0.
 *   looks good.
 *   let's try
 *
 */

#define int long long

typedef long long ll;

struct node {
    int s, e;
    ll mn, mx, sum;
    bool lset;
    ll add_val, set_val;
    node *l, *r;

    node(int _s, int _e, int A[] = nullptr) : s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0),
                                              l(nullptr), r(nullptr) {
        if (A == nullptr) return;
        if (s == e) mn = mx = sum = A[s];
        else {
            l = new node(s, (s + e) >> 1, A), r = new node((s + e + 2) >> 1, e, A);
            combine();
        }
    }

    void create_children() {
        if (s == e) return;
        if (l != nullptr) return;
        int m = (s + e) >> 1;
        l = new node(s, m);
        r = new node(m + 1, e);
    }

    void self_set(ll v) {
        lset = true;
        mn = mx = set_val = v;
        sum = v * (e - s + 1);
        add_val = 0;
    }

    void self_add(ll v) {
        if (lset) {
            self_set(v + set_val);
            return;
        }
        mn += v, mx += v, add_val += v;
        sum += v * (e - s + 1);
    }

    void lazy_propagate() {
        if (s == e) return;
        if (lset) {
            l->self_set(set_val), r->self_set(set_val);
            lset = set_val = 0;
        }
        if (add_val != 0) {
            l->self_add(add_val), r->self_add(add_val);
            add_val = 0;
        }
    }

    void combine() {
        if (l == nullptr) return;
        sum = l->sum + r->sum;
        mn = min(l->mn, r->mn);
        mx = max(l->mx, r->mx);
    }

    void add(int x, int y, ll v) {
        if (s == x && e == y) {
            self_add(v);
            return;
        }
        int m = (s + e) >> 1;
        create_children();
        lazy_propagate();
        if (x <= m) l->add(x, min(y, m), v);
        if (y > m) r->add(max(x, m + 1), y, v);
        combine();
    }

    void set(int x, int y, ll v) {
        if (s == x && e == y) {
            self_set(v);
            return;
        }
        int m = (s + e) >> 1;
        create_children();
        lazy_propagate();
        if (x <= m) l->set(x, min(y, m), v);
        if (y > m) r->set(max(x, m + 1), y, v);
        combine();
    }

    ll range_sum(int x, int y) {
        if (s == x && e == y) return sum;
        if (l == nullptr || lset) return (sum / (e - s + 1)) * (y - x + 1);
        int m = (s + e) >> 1;
        lazy_propagate();
        if (y <= m) return l->range_sum(x, y);
        if (x > m) return r->range_sum(x, y);
        return l->range_sum(x, m) + r->range_sum(m + 1, y);
    }

    ll range_min(int x, int y) {
        if (s == x && e == y) return mn;
        if (l == nullptr || lset) return mn;
        int m = (s + e) >> 1;
        lazy_propagate();
        if (y <= m) return l->range_min(x, y);
        if (x > m) return r->range_min(x, y);
        return min(l->range_min(x, m), r->range_min(m + 1, y));
    }

    ll range_max(int x, int y) {
        if (s == x && e == y) return mx;
        if (l == nullptr || lset) return mx;
        int m = (s + e) >> 1;
        lazy_propagate();
        if (y <= m) return l->range_max(x, y);
        if (x > m) return r->range_max(x, y);
        return max(l->range_max(x, m), r->range_max(m + 1, y));
    }

    ~node() {
        // note: deleting nullptr has no effect
        delete l;
        delete r;
    }
};

int n, q;
vector<int> A;
vector<vector<int>> memo;

node *root;

void init() {
    memo.clear();
    memo.resize(n, vector<int>(n, -1));
}

int value(int i, int j) {
    return root->range_max(i, j) - root->range_min(i, j);
}

int dp(int i, int j) {
    if (memo[i][j] != -1) return memo[i][j];
    if (i == j) return 0;

    int ans = value(i, j);
    for (int k = i + 1; k < j; k++) {
        ans = max(ans, dp(i,k) + dp(k+1, j));
    }

    //cerr << "dp ( " << i << " , " << j << " ) = " << ans << endl;
    return memo[i][j] = ans;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> q;
    A.resize(n);
    root = new node(0, n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        root->set(i, i, A[i]);
    }

    while (q--) {
        init();

        int l, r, delta; cin >> l >> r >> delta; l--, r--;
        root->add(l, r, delta);

        int ans = dp(0, n-1);
        cout << ans << "\n";
    }

    delete root;

}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55