oj.uz

Submission #1024047

# Submission time Handle Problem Language Result Execution time Memory
1024047 2024-07-15T10:47:23 Z kustizus Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 518 ms 33476 KB 
// #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

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.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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5 ms 2896 KB Output is correct
8 Correct 5 ms 2908 KB Output is correct
9 Correct 4 ms 2908 KB Output is correct
10 Correct 5 ms 2908 KB Output is correct
11 Correct 5 ms 2908 KB Output is correct
12 Correct 4 ms 2908 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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5 ms 2896 KB Output is correct
8 Correct 5 ms 2908 KB Output is correct
9 Correct 4 ms 2908 KB Output is correct
10 Correct 5 ms 2908 KB Output is correct
11 Correct 5 ms 2908 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct
13 Correct 518 ms 31864 KB Output is correct
14 Correct 391 ms 31828 KB Output is correct
15 Correct 412 ms 31824 KB Output is correct
16 Correct 474 ms 33476 KB Output is correct
17 Correct 458 ms 31572 KB Output is correct
18 Correct 432 ms 32336 KB Output is correct