oj.uz

Submission #1087565

# Submission time Handle Problem Language Result Execution time Memory
1087565 2024-09-13T01:16:29 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 372 ms 27984 KB 
#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_) for(int V_=(A_), V_##_END=(B_); V_>=V_##_END; V_--)
#ifdef _WIN32
#define long __int64
#endif
using namespace std;
const int MAXN=2e5+10; const long INFL=1e18;
int n,qn; long A[MAXN];
void tomax(long& x,long y){ x=max(x,y); }
struct SGT{
#define ls (u*2)
#define rs (u*2+1)
#define mid ((l+r)/2)
    struct{ long mx[2][2]; } T[MAXN*4];
    void pushup(int u,int l,int r){
        RNG(tl,0,1){
            RNG(tr,0,1){
                T[u].mx[tl][tr]=0;
                tomax(T[u].mx[tl][tr],T[ls].mx[tl][0]+T[rs].mx[0][tr]);
                tomax(T[u].mx[tl][tr],T[ls].mx[tl][0]+T[rs].mx[1][tr]);
                tomax(T[u].mx[tl][tr],T[ls].mx[tl][1]+T[rs].mx[0][tr]);
                if((A[mid]>=0&&A[mid+1]>=0)||(A[mid]<=0&&A[mid+1]<=0)) tomax(T[u].mx[tl][tr],T[ls].mx[tl][1]+T[rs].mx[1][tr]);
            }
        }
    }
    void build(int u,int l,int r){
        if(l==r){
            T[u].mx[0][0]=0,T[u].mx[1][1]=labs(A[l]);
            T[u].mx[0][1]=T[u].mx[1][0]=0;
            return;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(u,l,r);
    }
    void upd(int u,int l,int r,int i){
        if(l==r){
            T[u].mx[0][0]=0,T[u].mx[1][1]=labs(A[i]);
            T[u].mx[0][1]=T[u].mx[1][0]=0;
            return;
        }
        if(i<=mid) upd(ls,l,mid,i);
        else upd(rs,mid+1,r,i);
        pushup(u,l,r);
    }
#undef ls
#undef rs
#undef mid
} sgt;
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#else
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>qn;
    RNG(i,1,n) cin>>A[i];
    IRNG(i,n,1) A[i]-=A[i-1];
    sgt.build(1,2,n);
    RNG(_,1,qn){
        int l,r; long x; cin>>l>>r>>x;
        A[l]+=x,A[r+1]-=x;
        if(l>=2) sgt.upd(1,2,n,l);
        if(r+1<=n) sgt.upd(1,2,n,r+1);
        auto ans=max({sgt.T[1].mx[0][0],sgt.T[1].mx[0][1],sgt.T[1].mx[1][0],sgt.T[1].mx[1][1]});
        cout<<ans<<"\n";
    }
}

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 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 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 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 856 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 5 ms 856 KB Output is correct
12 Correct 3 ms 860 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 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 856 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 5 ms 856 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 357 ms 27472 KB Output is correct
14 Correct 372 ms 27472 KB Output is correct
15 Correct 320 ms 27348 KB Output is correct
16 Correct 349 ms 27464 KB Output is correct
17 Correct 344 ms 27204 KB Output is correct
18 Correct 360 ms 27984 KB Output is correct