Submission #1024047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024047		kustizus	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	518 ms	33476 KiB

Main

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,fma,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5;
int n,m,ar[N+5],Lz[4*N+5];
struct Node{
    int d[2][2];
} ST[4*N+5];
Node Merge(int md, Node a, Node b){
    if (b.d[0][0]==-1) return a;
    if (a.d[0][0]==-1) return b;
    Node c;
    for (int i=0;i<2;++i)
        for (int j=0;j<2;++j){
            c.d[i][j]=0;
            for (int x=0;x<2;++x)
                for (int y=0;y<2;++y){
                    int now=a.d[i][x]+b.d[y][j];
                    if (x==y && ((!x && ar[md]>=ar[md+1]) || (x && ar[md]<=ar[md+1])))
                        now+=abs(ar[md]-ar[md+1]);
                    c.d[i][j]=max(c.d[i][j],now);
                }
        }
    return c;
}
// 0: dãy tăng
// 1: dãy giảm
void Build(int id, int l, int r){
    if (l==r){
        for (int i=0;i<2;++i)
            for (int j=0;j<2;++j)
                ST[id].d[i][j]=(i==j ? 0 : -1e18);
        return;
    }
    int md=l+r>>1;
    Build(id<<1,l,md);
    Build(id<<1|1,md+1,r);
    ST[id]=Merge(md,ST[id<<1],ST[id<<1|1]);
}
void Pus(int id, int l, int r){
    if (!Lz[id]) return;
    if (l!=r){
        Lz[id<<1]+=Lz[id];
        Lz[id<<1|1]+=Lz[id];
    }
    if (l!=r){
        if (id&1) ar[l]+=Lz[id];
        else ar[r]+=Lz[id];
    }
    Lz[id]=0;
}
void Update(int id, int l, int r, int x, int y, int val){
    Pus(id,l,r);
    if (l>y || r<x) return;
    if (l>=x && r<=y){
        Lz[id]+=val;
        if (id&1) ar[r]+=Lz[id];
        else ar[l]+=Lz[id];
        Pus(id,l,r);
        return;
    }
    int md=l+r>>1;
    Update(id<<1,l,md,x,y,val);
    Update(id<<1|1,md+1,r,x,y,val);
    ST[id]=Merge(md,ST[id<<1],ST[id<<1|1]);
}
Node Get(int id, int l, int r, int x, int y){
    Pus(id,l,r);
    if (l>y || r<x) return {-1,-1,-1,-1};
    if (l>=x && r<=y) return ST[id];
    int md=l+r>>1;
    return Merge(md,Get(id<<1,l,md,x,y),Get(id<<1|1,md+1,r,x,y));
}
void Solve(){
    cin>>n>>m;
    for (int i=1;i<=n;++i) cin>>ar[i];
    Build(1,1,n);
    while (m--){
        int l,r,val;
        cin>>l>>r>>val;
        Update(1,1,n,l,r,val);
        Node x=Get(1,1,n,1,n);
        int ans=0;
        for (int i=0;i<2;++i)
            for (int j=0;j<2;++j)
                ans=max(ans,x.d[i][j]);
        cout<<ans<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen ("FILE.INP","r",stdin);
    // freopen ("FILE.OUT","w",stdout);
    int t=1;
    // cin>>t;
    while (t--) Solve();
    cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
}

Compilation message (stderr)

Main.cpp: In function 'void Build(long long int, long long int, long long int)':
Main.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int md=l+r>>1;
      |            ~^~
Main.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int md=l+r>>1;
      |            ~^~
Main.cpp: In function 'Node Get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     int md=l+r>>1;
      |            ~^~

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