oj.uz

Submission #862401

# Submission time Handle Problem Language Result Execution time Memory
862401 2023-10-18T07:58:43 Z velislavgarkov Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 610 ms 39140 KB 
#include <iostream>
using namespace std;
const int MAXN=2e5+10;
struct Node {
    long long dp[2][2];
    long long lef, ri;
};
Node tree[4*MAXN];
long long a[MAXN], dif[MAXN];
Node combine_node(Node a, Node b) {
    Node ans;
    ans.lef=a.lef; ans.ri=b.ri;
    bool fl;
    if ((a.ri<0 && b.lef<0) || (a.ri>0 && b.lef>0)) fl=true;
    else fl=false;
    for (int i=0;i<2;i++) {
        for (int j=0;j<2;j++) {
            ans.dp[i][j]=max(a.dp[i][0]+max(b.dp[1][j],b.dp[0][j]),a.dp[i][1]+b.dp[0][j]);
            if (fl) ans.dp[i][j]=max(ans.dp[i][j],a.dp[i][1]+b.dp[1][j]);
        }
    }
    return ans;
}
void build_tree(int node, int l, int r) {
    if (l==r) {
        tree[node].lef=tree[node].ri=dif[l];
        tree[node].dp[0][0]=0;
        tree[node].dp[0][1]=0;
        tree[node].dp[1][0]=0;
        tree[node].dp[1][1]=abs(dif[l]);
        return;
    }
    int mid=(l+r)/2;
    build_tree(node*2,l,mid);
    build_tree(node*2+1,mid+1,r);
    tree[node]=combine_node(tree[node*2],tree[node*2+1]);
}
void update(int node, int l, int r, int qind) {
    if (qind<l || qind>r) return;
    if (l==r) {
        tree[node].lef=tree[node].ri=dif[l];
        tree[node].dp[0][0]=0;
        tree[node].dp[0][1]=0;
        tree[node].dp[1][0]=0;
        tree[node].dp[1][1]=abs(dif[l]);
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,qind);
    update(node*2+1,mid+1,r,qind);
    tree[node]=combine_node(tree[node*2],tree[node*2+1]);
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<n;i++) {
        dif[i]=a[i+1]-a[i];
    }
    build_tree(1,1,n-1);
    int l, r;
    long long x;
    for (int i=0;i<q;i++) {
        cin >> l >> r >> x;
        if (l>1) {
            dif[l-1]+=x;
            update(1,1,n-1,l-1);
        }
        if (r<n) {
            dif[r]-=x;
            update(1,1,n-1,r);
        }
        long long ans=0;
        for (int j=0;j<2;j++) {
            for (int k=0;k<2;k++) ans=max(ans,tree[1].dp[j][k]);
        }
        cout << ans << endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 7 ms 4700 KB Output is correct
8 Correct 7 ms 4700 KB Output is correct
9 Correct 8 ms 4700 KB Output is correct
10 Correct 7 ms 4700 KB Output is correct
11 Correct 7 ms 4700 KB Output is correct
12 Correct 7 ms 4700 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 7 ms 4700 KB Output is correct
8 Correct 7 ms 4700 KB Output is correct
9 Correct 8 ms 4700 KB Output is correct
10 Correct 7 ms 4700 KB Output is correct
11 Correct 7 ms 4700 KB Output is correct
12 Correct 7 ms 4700 KB Output is correct
13 Correct 610 ms 38400 KB Output is correct
14 Correct 571 ms 38644 KB Output is correct
15 Correct 576 ms 38432 KB Output is correct
16 Correct 599 ms 38228 KB Output is correct
17 Correct 596 ms 38212 KB Output is correct
18 Correct 560 ms 39140 KB Output is correct