Submission #1007582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007582		dwuy	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	344 KiB

Main

/**   - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

struct Node{
    bool full, tl, tr; 
    int sum;
    pii fl, fr;
    Node(){
        this->full = 1;
        this->tl = this->tr = 0;
        this->sum = 0;
        this->fl = this->fr = {0, 0};
    }

    void combine(const Node &L, const Node &R){
        full = L.full && R.full && L.tr != R.tl;
        if(full){
            fr = fl = {L.fl.fi + R.fl.se, L.fl.se + R.fl.fi};
            tl = L.tl, tr = R.tr;
            sum = 0;
        }
        else{
            fl = L.fl, fr = R.fr;
            tl = L.tl, tr = R.tr;
            sum = L.sum + R.sum + (L.full? 0 : max(L.fr.fi, L.fr.se)) + (R.full? 0 : max(R.fl.fi, R.fl.se));
        }
    }
};

struct SMT{
    int n;
    vector<Node> tree;
    
    SMT(int n = 0){
        this->n = n;
        this->tree.assign(n<<2|3, Node());
    }

    void update(int pos, int val){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            if(pos <= mid) hi = mid, id <<= 1;
            else lo = mid + 1, id = id<<1 | 1;
        }
        tree[id].sum = 0;
        tree[id].full = 1;
        tree[id].tl = tree[id].tr = val < 0;
        tree[id].fl = tree[id].fr = {abs(val), 0};
        for(id>>=1; id; id>>=1){
            tree[id].combine(tree[id<<1], tree[id<<1|1]);
        }
    }

    int get(){
        if(tree[1].full) return max(tree[1].fl.fi, tree[1].fl.se);
        return tree[1].sum + max(tree[1].fl.fi, tree[1].fl.se) + max(tree[1].fr.fi, tree[1].fr.se);
    }

    void show(int l, int r, int id){
        if(l == r){
            cout << tree[id].sum << ", " << tree[id].fl.fi << ' ' << tree[id].fl.se << " -- " << tree[id].fr.fi << ' ' << tree[id].fr.se << " - " << l << ' ' << r << endl;
            return;
        }
        int mid = (l + r)>>1;
        show(l, mid, id<<1);
        show(mid+1, r, id<<1|1);
        cout << tree[id].sum << ", " << tree[id].fl.fi << ' ' << tree[id].fl.se << " -- " << tree[id].fr.fi << ' ' << tree[id].fr.se << " - " << l << ' ' << r << endl;

    }

    void show(){
        cout << endl;
        show(1, n, 1);
        cout << endl;
    }
};

struct BIT{
    int n;
    vector<int> tree;
    
    BIT(int n=0){
        this->n = n;
        this->tree.assign(n+5, 0);
    }

    void update(int idx, int val){
        for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
    }

    int get(int idx){
        int res = 0;
        for(; idx; idx-=-idx&idx) res += tree[idx];
        return res;
    }

    void update(int l, int r, int val){
        update(l, val); update(r+1, -val);
    }
};

const int MX = 200005;
int n, q;
int a[MX];

void nhap(){
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
}

void solve(){
    SMT smt(n - 1);
    BIT bit(n + 1);
    for(int i=1; i<=n; i++) bit.update(i, i, a[i]);
    for(int i=1; i<n; i++) smt.update(i, a[i+1] - a[i]);
    // smt.show();
    while(q--){
        int l, r, v;
        cin >> l >> r >> v;
        bit.update(l, r, v);
        if(l != 1) smt.update(l - 1, bit.get(l) - bit.get(l - 1));
        if(r < n) smt.update(r, bit.get(r + 1) - bit.get(r));      
        // smt.show();
        cout << smt.get() << endl;
    }
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

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