oj.uz

Submission #402461

# Submission time Handle Problem Language Result Execution time Memory
402461 2021-05-11T17:45:34 Z NintsiChkhaidze Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 847 ms 109048 KB 
#include <bits/stdc++.h>
#define ll long long
#define left (node<<1),l,(l+r)>>1
#define right ((node<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 200005;
ll sgt[4*N][5][5],a[N],b[N];
void go(int node){
    ll x = sgt[(node<<1)][0][2],y = sgt[((node<<1)|1)][2][0];
    
    for (int i=0;i<=1;i++)
        for (int j=0;j<=1;j++){
            ll m=0;
            for (int o=0;o<=1;o++)
                for (int v=0;v<=1;v++){
                    sgt[node][i][j] = sgt[(node<<1)][i][o] + sgt[((node<<1)|1)][v][j];
                    if (x*y >= 0 || o*v != 1) m = max(m,sgt[node][i][j]); 
                }
            sgt[node][i][j] = m;
        }
    sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
    sgt[node][2][0] = sgt[(node<<1)][2][0];
}
void build(int node,int l,int r){
    if (l == r){
        sgt[node][1][1] = abs(b[l]);
        sgt[node][1][0] = sgt[node][0][1] = sgt[node][0][0] = 0;
        sgt[node][2][0] = sgt[node][0][2] = b[l];
        return;
    }
    build(left),build(right);
    go(node);
}
void upd(int node,int l,int r,int ind){
    if (l == r){
        sgt[node][1][1] = abs(b[l]);
        sgt[node][1][0] = sgt[node][0][1] = sgt[node][0][0] = 0;
        sgt[node][2][0] = sgt[node][0][2] = b[l];
        return;
    }
    if (ind > ((l+r)>>1)) upd(right,ind);
    else upd(left,ind);
    go(node);
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n,q;
    cin>>n>>q;
    
    for (int i=1;i<=n;i++)
        cin>>a[i];
    
    for (int i=1;i<n;i++)
        b[i] = a[i]-a[i+1];
       
    build(1,1,n-1);
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        if (l > 1) b[l-1]-=k,upd(1,1,n-1,l-1);
        if (r < n) b[r]+=k,upd(1,1,n-1,r);
        
        ll x = max(max(sgt[1][1][1],sgt[1][0][0]),max(sgt[1][1][0],sgt[1][0][1]));
        cout<<x<<"\n";
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 6 ms 1996 KB Output is correct
8 Correct 6 ms 1996 KB Output is correct
9 Correct 6 ms 1996 KB Output is correct
10 Correct 7 ms 1996 KB Output is correct
11 Correct 6 ms 2000 KB Output is correct
12 Correct 6 ms 1992 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 6 ms 1996 KB Output is correct
8 Correct 6 ms 1996 KB Output is correct
9 Correct 6 ms 1996 KB Output is correct
10 Correct 7 ms 1996 KB Output is correct
11 Correct 6 ms 2000 KB Output is correct
12 Correct 6 ms 1992 KB Output is correct
13 Correct 749 ms 108812 KB Output is correct
14 Correct 841 ms 108908 KB Output is correct
15 Correct 847 ms 108912 KB Output is correct
16 Correct 806 ms 109048 KB Output is correct
17 Correct 775 ms 108864 KB Output is correct
18 Correct 755 ms 108948 KB Output is correct