oj.uz

Submission #971358

# Submission time Handle Problem Language Result Execution time Memory
971358 2024-04-28T11:53:23 Z KawakiMeido Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 288 ms 50768 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define int long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 2e5+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

struct Node{
    int dp00,dp01,dp10,dp11,l,r;

    Node(): dp00{0}, dp01{0}, dp10{0}, dp11{0}{};

    void Init(int val){
        dp11 = abs(val);
        l = val;
        r = val;
    }
};

/*Global Variables*/
int n,q;
int a[N],d[N];
Node IT[N*4];

void Comb(Node& x, Node& l, Node& r){
    x.l = l.l;
    x.r = r.r;
    if (l.r*r.l<0){
        x.dp00 = max(l.dp00+r.dp10,l.dp01+r.dp00);
        x.dp01 = max(l.dp00+r.dp11,l.dp01+r.dp01);
        x.dp10 = max(l.dp10+r.dp10,l.dp11+r.dp00);
        x.dp11 = max(l.dp10+r.dp11,l.dp11+r.dp01);
    }
    else{
        x.dp00 = l.dp01+r.dp10;
        x.dp01 = l.dp01+r.dp11;
        x.dp10 = l.dp11+r.dp10;
        x.dp11 = l.dp11+r.dp11;
    }
}

void Build(int idx, int l, int r){
    if (l == r){
        IT[idx].Init(d[l]);
        return;
    }
    int mid = (l+r)/2;
    Build(idx*2,l,mid); Build(idx*2+1,mid+1,r);
    Comb(IT[idx],IT[idx*2],IT[idx*2+1]);
}

void Update(int idx, int l, int r, int x, int val){
    if (x < l || r < x) return;
    if (l == r){
        IT[idx].Init(IT[idx].l+val);
        return;
    }
    int mid = (l+r)/2;
    Update(idx*2,l,mid,x,val); Update(idx*2+1,mid+1,r,x,val);
    Comb(IT[idx],IT[idx*2],IT[idx*2+1]);
}

/*Solution*/
void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        d[i-1] = a[i] - a[i-1];
    }
    a[0] = 0;
    --n;
//    cout << endl;
    Build(1,1,n);
    while (q--){
        int l,r,x;
        cin >> l >> r >> x;
        if (l!=1){
            d[l-1]+=x;
            Update(1,1,n,l-1,x);
        }
        if (r!=n+1){
            d[r]-=x;
            Update(1,1,n,r,-x);
        }
//        for (int i=1; i<=n; i++){
//            cout << d[i] << " ";
//        }
//        cout << endl;
        cout << max({IT[1].dp00,IT[1].dp01,IT[1].dp10,IT[1].dp11}) << endl;
//        cout << IT[1].dp00 << " " << IT[1].dp01 << " " << IT[1].dp10 << " " << IT[1].dp11 << " " << endl;
    }
}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39512 KB Output is correct
2 Correct 7 ms 39516 KB Output is correct
3 Correct 6 ms 39516 KB Output is correct
4 Correct 7 ms 39516 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 6 ms 39600 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39512 KB Output is correct
2 Correct 7 ms 39516 KB Output is correct
3 Correct 6 ms 39516 KB Output is correct
4 Correct 7 ms 39516 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 6 ms 39600 KB Output is correct
7 Correct 9 ms 39512 KB Output is correct
8 Correct 8 ms 39768 KB Output is correct
9 Correct 8 ms 39516 KB Output is correct
10 Correct 9 ms 39640 KB Output is correct
11 Correct 8 ms 39516 KB Output is correct
12 Correct 8 ms 39516 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39512 KB Output is correct
2 Correct 7 ms 39516 KB Output is correct
3 Correct 6 ms 39516 KB Output is correct
4 Correct 7 ms 39516 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 6 ms 39600 KB Output is correct
7 Correct 9 ms 39512 KB Output is correct
8 Correct 8 ms 39768 KB Output is correct
9 Correct 8 ms 39516 KB Output is correct
10 Correct 9 ms 39640 KB Output is correct
11 Correct 8 ms 39516 KB Output is correct
12 Correct 8 ms 39516 KB Output is correct
13 Correct 283 ms 50204 KB Output is correct
14 Correct 268 ms 50264 KB Output is correct
15 Correct 259 ms 50260 KB Output is correct
16 Correct 270 ms 50120 KB Output is correct
17 Correct 288 ms 50004 KB Output is correct
18 Correct 252 ms 50768 KB Output is correct