oj.uz

Submission #1007597

# Submission time Handle Problem Language Result Execution time Memory
1007597 2024-06-25T08:48:07 Z dwuy Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 272 ms 44368 KB 
/**   - 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 3 ms 1112 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 3 ms 1112 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 272 ms 44004 KB Output is correct
14 Correct 238 ms 43976 KB Output is correct
15 Correct 261 ms 43860 KB Output is correct
16 Correct 255 ms 43836 KB Output is correct
17 Correct 229 ms 43860 KB Output is correct
18 Correct 223 ms 44368 KB Output is correct