Submission #1007597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007597		dwuy	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	272 ms	44368 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 tl, tr; 
    int f[4];
    Node(){
        this->tl = this->tr = 0;
        memset(this->f, 0, sizeof this->f);
    }

    void combine(const Node &L, const Node &R){
        tl = L.tl, tr = R.tr;
        if(L.tr != R.tl){
            f[0b00] = max(max(L.f[0b00], L.f[0b01]) + R.f[0b00], L.f[0b00] + max(R.f[0b10], R.f[0b00]));
            f[0b01] = max(max(L.f[0b00], L.f[0b01]) + R.f[0b01], L.f[0b00] + max(R.f[0b11], R.f[0b01]));
            f[0b10] = max(max(L.f[0b10], L.f[0b11]) + R.f[0b00], L.f[0b10] + max(R.f[0b10], R.f[0b00]));
            f[0b11] = max(max(L.f[0b10], L.f[0b11]) + R.f[0b01], L.f[0b10] + max(R.f[0b11], R.f[0b01]));
        }
        else{
            f[0b00] = max(L.f[0b00], L.f[0b01]) + max(R.f[0b10], R.f[0b00]);
            f[0b01] = max(L.f[0b00], L.f[0b01]) + max(R.f[0b11], R.f[0b01]);
            f[0b10] = max(L.f[0b10], L.f[0b11]) + max(R.f[0b10], R.f[0b00]);
            f[0b11] = max(L.f[0b10], L.f[0b11]) + max(R.f[0b11], R.f[0b01]);
        }
    }
};

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].tl = tree[id].tr = val < 0;
        tree[id].f[0b00] = 0;
        tree[id].f[0b11] = abs(val);
        for(id>>=1; id; id>>=1){
            tree[id].combine(tree[id<<1], tree[id<<1|1]);
        }
    }

    int get(){
        return max({tree[1].f[0], tree[1].f[1], tree[1].f[2], tree[1].f[3]});
    }

    void show(int l, int r, int id){
        if(l == r){
            cerr << tree[id].tl << ' ' << tree[id].tr << " -- " << tree[id].f[0] << ' ' << tree[id].f[1] << ' ' << tree[id].f[2] << ' ' << tree[id].f[3] << " - " << l << ' ' << r << endl;
            return;
        }
        int mid = (l + r)>>1;
        show(l, mid, id<<1);
        show(mid+1, r, id<<1|1);
        cerr << tree[id].tl << ' ' << tree[id].tr << " -- " << tree[id].f[0] << ' ' << tree[id].f[1] << ' ' << tree[id].f[2] << ' ' << tree[id].f[3] << " - " << 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;
}

/*

6 3
1 2 5 4 6 8
2 5 0
4 4 1
2 5 -2

7 1
1 5 2 8 1 7 1
2 6 0


*/

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