Submission #631823

#	Time	Username	Problem	Language	Result	Execution time	Memory
631823		timg8710	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	772 ms	58664 KiB

Main

//@timothyg

#include <bits/stdc++.h>
using namespace std;
 
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << '{' << p.first << ", " << p.second << '}';
}

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
  os << '[';
  for (auto it = c.begin(); it != c.end(); ++it)
    os << &", "[2 * (it == c.begin())] << *it;
  return os << ']';
}
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
  _NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0)     \
  (MACRO, ##__VA_ARGS__)
#define DBG_OUT(x) #x " = " << x << "; "
#define dbg(...)                                                              \
  cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(DBG_OUT, __VA_ARGS__) << '\n'


typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define vsz(a) (int)a.size()
#define f first
#define s second

struct node{
    int isDummy = 0;

    ll borders[2] = {0, 0}; //border values of segment
    ll dp[2][2] = {{0,0}, {0,0}}; //take/not-take left and right border values

    node(){}
    node(ll v){
        borders[0] = borders[1] = v;
        dp[0][1] = dp[1][0] = dp[0][0] = 0;
        dp[1][1] = abs(v);
    }
    //assume current is left
    node comb(node& other){
        node ret;

        ret.borders[0] = borders[0];
        ret.borders[1] = other.borders[1];

        //[    ][     ]
        //l    mo     r
        //m and o same means the taken segments are combined
        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(m && o){
                            //it's never optimal to take two opposite sign values
                            if((borders[1] < 0) == (other.borders[0] < 0)){
                                ret.dp[l][r] = max(ret.dp[l][r], dp[l][m] + other.dp[o][r]);
                            }
                        }else{
                            ret.dp[l][r] = max(ret.dp[l][r], dp[l][m] + other.dp[o][r]);
                        }
                    }
                }
            }
        }

        return ret;
    }

    //modify a single-element node range + v
    void upd(ll v){
        borders[0] += v;
        borders[1] += v;
        dp[1][1] = abs(borders[0]);
    }
};

struct segtree
{
    node val;
    int gL, gR, mid;
    segtree *left, *right;

    segtree(int l, int r, vector<node>& nums)
    {
        gL = l; gR = r; mid = (gL+gR)/2;
        if (l == r)
        {
            val = nums[l];
        }
        else
        {
            
            left = new segtree(l, mid, nums), right = new segtree(mid + 1, r, nums);
            val = left->val.comb(right->val);
        }
    }

    node query(int l, int r)
    {

        if (gL > r || gR < l)
        {
            node dummy; dummy.isDummy=1;
            return dummy;
        }

        if (gL == l && gR == r)
        {
            return val;
        }
        node a = left->query(l, min(r, mid)), b = right->query(max(l, mid + 1), r);
        if(a.isDummy) return b;
        if(b.isDummy) return a;
        return a.comb(b);
    }

    void update(int idx, ll updval)
    {
        if (gL == gR)
        {
            val.upd(updval);
        }
        else
        {
            if (idx <= (gL + gR) / 2)
            {
                left->update(idx, updval);
            }
            else
            {
                right->update(idx, updval);
            }
            val = left->val.comb(right->val);
        }
   }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    int N, Q; cin >> N >> Q;
    vector<node> D(N-1);
    int a; cin >> a;
    //compute difference arrays
    for(int i = 0; i<N-1; i++){
        int b; cin >> b;
        D[i] = node(b - a);
        swap(a, b);
    }
    
    //a_(i+1) - a(i)
    segtree sgt(0, N-2, D);
    // for (int j = 0; j < N-1; j++){
    //         dbg(sgt.query(j, j).borders[0], sgt.query(j, j).borders[1]);
    //     }
        //-2 2 -1
    for(int q = 0; q<Q; q++){
        int l, r; ll x; cin >> l >> r >> x;
        l--, r--;
        if(l-1 >= 0){
            sgt.update(l-1, x); //a_(i+1) is changed
        }
        if(r < N-1){
            sgt.update(r, -x); //ai is changed
        }
        // for (int j = 0; j < N-1; j++){
        //     dbg(sgt.query(j, j).borders[0], sgt.query(j, j).borders[1]);
        // }
        // cout << endl;
        cout << max(
            {sgt.val.dp[0][0], sgt.val.dp[0][1], sgt.val.dp[1][0], sgt.val.dp[1][1]}
        ) << '\n';
    }

    return 0;
}

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