Submission #1289365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289365		vinren	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1 ms	332 KiB

Main

#include <bits/stdc++.h>
#include <complex>
#define vec vector
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fs first
#define sc second
#define ll long long
#define ld long double
#define lcm(x,y) (x)*(y)/__gcd(x,y);
#define all(vctr) vctr.begin(), vctr.end()
#define rall(vctr) vctr.rbegin(), vctr.rend()

template<class A, class B> std::ostream& operator<<(std::ostream& os, const std::pair<A,B>& p){ return os<<"("<<p.first<<","<<p.second<<")"; }
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v){ os<<"["; for(auto it=v.begin(); it!=v.end(); ++it){ if(it!=v.begin()) os<<","; os<<*it; } return os<<"]"; }
template<class T> std::ostream& operator<<(std::ostream& os, const std::set<T>& s){ os<<"{"; for(auto it=s.begin(); it!=s.end(); ++it){ if(it!=s.begin()) os<<","; os<<*it; } return os<<"}"; }

void DBG() { std::cerr << "]" << std::endl; }
template <class T, class... U> void DBG(const T &t, const U &...u) {
	std::cerr << t; if (sizeof...(u)) std::cerr << ", "; DBG(u...);
}
#define dbg(...) std::cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);

using namespace std;

// Multiple test cases or not
// #define BATCH true
// #define BATCH_WHILE_TRUE true
#define int ll

#ifdef BATCH_WHILE_TRUE
void endtc() {
    exit(0);
}
#endif


#define LDIR 0
#define RDIR 1

#define DECR 0
#define INCR 1
#define CONT 2
#define getdir(val) (val==0 ? CONT : (val>0 ? INCR : DECR))


const ll INF = 1e18;

struct Node {
    // Within dp: 0 means removed, 1 stays
    // dp[0][0] removed l r, dp[1][0] removed r, etc.
    // dp[i][j] means if end state is: left=i and right=j, whats the minimum cost? 
    ll dp[2][2];
    int dir[2];
    ll sum;
    Node() { dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=INF; dir[LDIR]=dir[RDIR]=CONT; sum=-1; }
    Node(int x): Node() {
        dp[0][0]=abs(x);
        dp[1][1]=0;
        dir[LDIR]=dir[RDIR]=getdir(x);
        sum=abs(x);
    }
    inline ll getval() {
        return sum-min({dp[0][0],dp[0][1],dp[1][0],dp[1][1]});
    }
};


struct segment_tree {
    ll SZ=1;
    vector<Node> arr;
    Node default_value = Node();
    segment_tree(int _sz=(int)2.5e5) {
        while (SZ<_sz) {SZ<<=1;}
        arr.resize(SZ<<1);
        for (auto& x:arr) x=default_value;
    }

    Node merge(Node le, Node ri) {
        if (le.sum==-1) return ri;
        if (ri.sum==-1) return le;
        Node res;
        if (le.dir[RDIR]==CONT || ri.dir[LDIR]==CONT || le.dir[RDIR]==ri.dir[LDIR]) {
            for (int i=0;i<2;i++) {
                for (int j=0;j<2;j++) {
                    res.dp[i][j]=INF;
                    for (int k=0;k<2;k++) {
                        for (int l=0;l<2;l++) {
                            res.dp[i][j]=min(res.dp[i][j],le.dp[i][k]+ri.dp[l][j]);
                            // dbg(i,j,k,l);
                        }
                    }
                }
            }
        } else {
            // adj must be different
            for (int i=0;i<2;i++) {
                for (int j=0;j<2;j++) {
                    res.dp[i][j]=4e18;
                    for (int k=0;k<2;k++) {
                        res.dp[i][j]=min(res.dp[i][j],le.dp[i][k]+ri.dp[k^1][j]);
                        // dbg(i,j,k);
                    }
                }
            }
        }
        res.dir[LDIR]=le.dir[LDIR];
        res.dir[RDIR]=ri.dir[RDIR];
        res.sum=le.sum+ri.sum;
        // dbg("done");
        return res;
    }

    void update(ll idx, ll val) {
        ll nd=idx+SZ;
        arr[nd]=Node(val);
        while (nd>1) { //update par
            nd/=2;
            arr[nd] = merge(arr[2*nd], arr[2*nd+1]);
        }
    }

    Node query(ll nd, ll cl, ll cr, ll ql, ll qr) {
        if (ql<=cl && cr<=qr) return arr[nd];
        else if (cl>qr || cr<ql) return default_value;
        else {
            ll mid = (cl+cr)/2;
            return merge(query(2*nd, cl, mid, ql, qr), query(2*nd+1, mid+1, cr, ql, qr));
        }
    }
};


void init() {
}

void solve() {
    int n,q;cin>>n>>q;
    vec<int> a(n);
    for (auto&e:a) cin>>e;
    segment_tree st(n-1);
    vec<int> dif(n-1);
    for (int i=0;i<n-1;i++) {
        dif[i]=a[i+1]-a[i];
        st.update(i, a[i+1]-a[i]);
    }

    while (q--) {
        int l,r,x;cin>>l>>r>>x;
        l--,r--;
        if (l-1>=0) {
            dif[l-1]+=x;
            st.update(l-1, dif[l-1]);
        }
        if (r<n-1) {
            dif[r]-=x;
            st.update(r, dif[r]);
        }
        Node res = st.query(1, 0, st.SZ-1, 0, n-1);
        // dbg(res.sum, res.dp[0][0], res.dp[0][1], res.dp[1][0], res.dp[1][1]);
        cout<<res.getval()<<'\n';
    }
}


signed main() {
    // freopen("heavy.in", "r", stdin);
    // freopen("heavy.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    init();
    int t=1;
    #ifdef BATCH
    cin >> t;
    #endif
    #ifdef BATCH_WHILE_TRUE
    while (true) solve();
    #else
    while (t--) solve();
    #endif
}

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