oj.uz

Submission #866742

# Submission time Handle Problem Language Result Execution time Memory
866742 2023-10-27T01:50:13 Z hqminhuwu Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 357 ms 43100 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e18;
const ll mod = 1e9 + 7;

struct node {
    ll l,r,uu,vv,uv,vu;
    node operator + (node a){
        node k;
        k.uu = max (uu + a.uu,max (uv + a.uu,max(uu + a.vu,uv + a.vu)));
        k.vv = max (vu + a.uv,max (vv + a.uv,max(vu + a.vv,vv + a.vv)));
        k.uv = max (uu + a.uv,max (uv + a.uv,max(uu + a.vv,uv + a.vv)));
        k.vu = max (vu + a.uu,max (vv + a.uu,max(vu + a.vu,vv + a.vu)));
        if (r <= a.l){
            k.uu = max (k.uu,uu + a.uu + a.l - r);
            k.vv = max (k.vv,vu + a.uv + a.l - r);
            k.uv = max (k.uv,uu + a.uv + a.l - r);
            k.vu = max (k.vu,vu + a.uu + a.l - r);
        }
        else {
            k.uu = max (k.uu,uv + a.vu - a.l + r);
            k.vv = max (k.vv,vv + a.vv - a.l + r);
            k.uv = max (k.uv,uv + a.vv - a.l + r);
            k.vu = max (k.vu,vv + a.vu - a.l + r);
        }
        k.l = l;
        k.r = a.r;
        return k;
    }
};

node tree[4 * N];
ll lazy[4 * N],a[N];

void down (int i){
    if (lazy[i] == 0) return;
    lazy[(i << 1)] += lazy[i];
    lazy[(i << 1) | 1] += lazy[i];
    tree[(i << 1)].l += lazy[i];
    tree[(i << 1)].r += lazy[i];
    tree[(i << 1) | 1].l += lazy[i];
    tree[(i << 1) | 1].r += lazy[i];
    lazy[i] = 0;
}
void build (int i, int l, int r){
    if (l == r){
        tree[i] = {a[l],a[l],0,0,-oo,-oo};
        return;
    }
    int mid = (l + r) >> 1;
    build ((i << 1), l, mid);
    build ((i << 1) | 1, mid + 1, r);
    tree[i] = (tree[(i << 1)] + tree[(i << 1) | 1]);
    // cout << l << " " << r << " " << tree[i].l << " " << tree[i].r << " " << tree[i].uu << " " << tree[i].vv
    // << " " << tree[i].uv << " " << tree[i].vu << "\n";
}
void update (int i, int l, int r, int u, int v, ll val){
    if (l > v || r < u)
        return;
    if (l >= u && r <= v){
        tree[i].l += val;
        tree[i].r += val;
        lazy[i] += val;
        return;
    }
    down(i);
    int mid = (l + r) >> 1;
    update((i << 1),l,mid,u,v,val);
    update((i << 1) | 1, mid + 1,r,u,v,val);
    tree[i] = (tree[(i << 1)] + tree[(i << 1) | 1]);
}
ll n,i,q,j,k;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    forr (i,1,n)
        cin >> a[i];
    build(1,1,n);
    // ll tmp1 = max (tree[1].uu,tree[1].vv);
    //     ll tmp2 = max (tree[1].uv,tree[1].vu);
    //     cout << max (tmp1,tmp2) << "\n";
    while (q--){
        cin >> i >> j >> k;
        update(1,1,n,i,j,k);
        ll tmp1 = max (tree[1].uu,tree[1].vv);
        ll tmp2 = max (tree[1].uv,tree[1].vu);
        cout << max (tmp1,tmp2) << "\n";
    }
    return 0;
}
/*



*/

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 328 ms 36124 KB Output is correct
14 Correct 322 ms 42396 KB Output is correct
15 Correct 357 ms 42576 KB Output is correct
16 Correct 318 ms 42324 KB Output is correct
17 Correct 328 ms 42340 KB Output is correct
18 Correct 314 ms 43100 KB Output is correct