Submission #1285222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285222		alizhan	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	590 ms	29544 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod =  1e9 + 7;
const int N = (int)2e5 + 7;
#define skip continue
#define uno first
#define duo second
#define GO while(tt--)
#define ins insert
#define pb push_back
#define all(x) x.begin(), x.end()
#define Kaldun ios::sync_with_stdio(false); cin.tie(nullptr)
#define int long long

int bp(int a, int n) {
    if(n == 0) return 1;
    if(n % 2 == 1) return (bp(a, n-1) * a) % mod;
    long long b = bp(a, n/2);
    return (b * b) % mod;
}

int dp[N * 4][2][2], tl[N * 4], tr[N * 4];
int a[N], b[N];
void f(int v, int l, int r) {
    int tm = (l + r) / 2;
    tl[v] = tl[v*2];
    tr[v] = tr[v*2+1];
    for(int i = 0;i < 2;i++){
        for(int j = 0;j < 2;j++){
            dp[v][i][j] = 0;
        }
    }
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 2; k++){
                for(int l = 0; l < 2; l++){
                    if(j == 1 && k == 1){
                        if((tr[v + v] < 0) == (tl[v + v + 1] < 0)){
                            dp[v][i][l] = max(dp[v][i][l], dp[v + v][i][j] + dp[v + v + 1][k][l]);
                        }
                    }
                    else{
                        dp[v][i][l] = max(dp[v][i][l], dp[v + v][i][j] + dp[v + v + 1][k][l]);
                    }
                }
            }
        }
    }
}
void upd(int v,int l,int r,int id,int x){
    if(id < l || r < id) return;
    if(l == r){
        tl[v] += x;
        tr[v] += x;
        dp[v][1][1] = abs(tl[v]);
        return;
    }
    int m = (l + r) / 2;
    upd(v + v, l, m, id, x);
    upd(v + v + 1, m + 1, r, id, x);
    f(v, l, r);
}
int lcm(int a,int b){ return (a * b) / __gcd(a,b);}
void solve() {
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        if(i >= 2){
            upd(1, 1, n - 1, i - 1, a[i] - a[i - 1]);
        }
    }
    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        if(l - 1 >= 1) upd(1,1,n - 1,l - 1,x);
        if(r < n) upd(1,1,n - 1,r,-x);
        cout<<dp[1][1][1]<<'\n';
    }
}
signed main() {
    Kaldun;
    cout.precision(0);
    //freopen("time.in", "r", stdin);
    //freopen("time.out", "w", stdout);
    int tt=1;
    //cin>>tt;
    while(tt--){
        solve();
    }
}

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