oj.uz

답안 #870942

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870942 2023-11-09T14:15:03 Z Ahmed57 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 822 ms 38476 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int borders[2] , dp[2][2];
}seg[800001];
node combine(node a ,node b){
    node res;
    res.borders[0] = a.borders[0];
    res.borders[1] = b.borders[1];
    for(int i = 0;i<2;i++)for(int j = 0;j<2;j++)res.dp[i][j] = 0;
    for(int l = 0;l<2;l++){
        for(int m = 0;m<2;m++){
            for(int o = 0;o<2;o++){
                for(int r = 0;r<2;r++){
                    if(m&o){
                        if((a.borders[1]<0)==(b.borders[0]<0)){
                            res.dp[l][r] = max(res.dp[l][r],a.dp[l][m]+b.dp[o][r]);
                        }
                    }else{
                        res.dp[l][r] = max(res.dp[l][r],a.dp[l][m]+b.dp[o][r]);
                    }
                }
            }
        }
    }
    return res;
}
int arr[200001];
void build(int p,int l,int r){
    if(l==r){
        seg[p].borders[0] = seg[p].borders[1] = arr[l];
        seg[p].dp[0][0] = 0;
        seg[p].dp[0][1] = 0;
        seg[p].dp[1][0] = 0;
        seg[p].dp[1][1] = abs(arr[l]);
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
void update(int p,int l,int r,int idx){
    if(l==r){
        seg[p].borders[0] = seg[p].borders[1] = arr[l];
        seg[p].dp[0][0] = 0;
        seg[p].dp[0][1] = 0;
        seg[p].dp[1][0] = 0;
        seg[p].dp[1][1] = abs(arr[l]);
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx);
    else update(p*2+1,md+1,r,idx);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,q;
    cin>>n>>q;
    int vl[n+1];
    for(int i = 1;i<=n;i++)cin>>vl[i];
    for(int i = 1;i<n;i++){
        arr[i] = vl[i+1]-vl[i];
    }
    build(1,1,n-1);
    while(q--){
        int l,r,x;cin>>l>>r>>x;
        if(l>1){
            arr[l-1]+=x;
            update(1,1,n-1,l-1);
        }if(r<n){
            arr[r]-=x;
            update(1,1,n-1,r);
        }
        cout<<max({seg[1].dp[0][0],seg[1].dp[1][0],seg[1].dp[0][1],seg[1].dp[1][1]})<<endl;
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 8 ms 2652 KB Output is correct
8 Correct 8 ms 2484 KB Output is correct
9 Correct 8 ms 2676 KB Output is correct
10 Correct 8 ms 2652 KB Output is correct
11 Correct 8 ms 2652 KB Output is correct
12 Correct 10 ms 2652 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 8 ms 2652 KB Output is correct
8 Correct 8 ms 2484 KB Output is correct
9 Correct 8 ms 2676 KB Output is correct
10 Correct 8 ms 2652 KB Output is correct
11 Correct 8 ms 2652 KB Output is correct
12 Correct 10 ms 2652 KB Output is correct
13 Correct 754 ms 37924 KB Output is correct
14 Correct 822 ms 38148 KB Output is correct
15 Correct 764 ms 38104 KB Output is correct
16 Correct 779 ms 37900 KB Output is correct
17 Correct 797 ms 37868 KB Output is correct
18 Correct 745 ms 38476 KB Output is correct