oj.uz

Submission #1016005

# Submission time Handle Problem Language Result Execution time Memory
1016005 2024-07-07T09:29:33 Z dosts Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 322 ms 60124 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define vvi vector<vi>
const int N = 4e5+1,inf = 2e18,B = 23,MOD = 998244353,LIM = 1e9;    
struct Node {
    int bas,son,yy,yn,ny,nn;
};

vi a(N),b(N);

Node merge(Node x,Node y) {
    Node ret;
    ret.bas = x.bas,ret.son = y.son;
    ret.yy = max(x.yy,x.yn)+max(y.yy,y.ny);
    ret.yn = max(x.yy,x.yn)+max(y.yn,y.nn);
    ret.ny = max(x.ny,x.nn)+max(y.ny,y.yy);
    ret.nn = max(x.nn,x.ny)+max(y.nn,y.yn);
    int d = x.son - y.bas;
    ret.yy = max(ret.yy,(x.yn+y.ny)+d);
    ret.yn = max(ret.yn,(x.yn+y.nn)+d);
    ret.ny = max(ret.ny,(x.nn+y.ny)+d);
    ret.nn = max(ret.nn,(x.nn+y.nn)+d);
    d = y.bas - x.son;
    ret.yy = max(ret.yy,(x.yy+y.yy)+d);
    ret.yn = max(ret.yn,(x.yy+y.yn)+d);
    ret.ny = max(ret.ny,(x.ny+y.yy)+d);
    ret.nn = max(ret.nn,(x.ny+y.yn)+d);
    return ret; 
}


struct ST {
    vector<Node> t;
    vi lazy;
    void build(int node,int l,int r) {
        if (l == r) {
            t[node] = {a[l],a[l],0,-inf,-inf,0};
            return;
        }
        int m = (l+r) >> 1;
        build(2*node,l,m),build(2*node+1,m+1,r);
        t[node] = merge(t[2*node],t[2*node+1]);
    }
    void push(int node,bool leaf) {
        t[node].bas+=lazy[node];
        t[node].son+=lazy[node];
        if (!leaf) {
            lazy[2*node]+=lazy[node];
            lazy[2*node+1]+=lazy[node];
        }
        lazy[node] = 0;
    }
    ST(int nn) {
        t.resize(4*nn+1);
        lazy.assign(4*nn+1,0);
        build(1,1,nn);
    } 

    void update(int node,int l,int r,int L,int R,int v) {
        push(node,l==r);
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            lazy[node] += v;
            push(node,l==r);
            return;
        }
        int m = (l+r) >> 1;
        update(2*node,l,m,L,R,v),update(2*node+1,m+1,r,L,R,v);
        t[node] = merge(t[2*node],t[2*node+1]);
    }
    Node query(int node,int l,int r,int L,int R) {
        push(node,l==r);
        return t[node];
    }
};
void solve() {
    int n,q;
    cin >> n >> q;
    for (int i=1;i<=n;i++) cin >> a[i];
    ST st(n);
    while (q--) {
        int l,r,v;
        cin >> l >> r >> v;
        st.update(1,1,n,l,r,v);
        Node nn = st.query(1,1,n,1,n);
        cout << max({nn.yy,nn.nn,nn.ny,nn.yn}) << '\n';
    }
}


                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #else 
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6764 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 6 ms 7768 KB Output is correct
8 Correct 5 ms 7512 KB Output is correct
9 Correct 6 ms 7260 KB Output is correct
10 Correct 6 ms 7328 KB Output is correct
11 Correct 5 ms 7512 KB Output is correct
12 Correct 5 ms 7512 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6764 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 6 ms 7768 KB Output is correct
8 Correct 5 ms 7512 KB Output is correct
9 Correct 6 ms 7260 KB Output is correct
10 Correct 6 ms 7328 KB Output is correct
11 Correct 5 ms 7512 KB Output is correct
12 Correct 5 ms 7512 KB Output is correct
13 Correct 316 ms 59480 KB Output is correct
14 Correct 322 ms 59628 KB Output is correct
15 Correct 285 ms 59444 KB Output is correct
16 Correct 312 ms 59484 KB Output is correct
17 Correct 313 ms 59528 KB Output is correct
18 Correct 303 ms 60124 KB Output is correct