oj.uz

Submission #440423

# Submission time Handle Problem Language Result Execution time Memory
440423 2021-07-02T09:06:29 Z leaked Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 574 ms 30708 KB 
#include <bits/stdc++.h>

#define vec vector
#define f first
#define s second
#define endl '\n'
#define pb push_back
#define sz(x) (int)x.size()
#define umax(a,b) a=max(a,b)

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const ll inf=1e18;
const int N=2e5+1;
pii to[2][2][2][2];
struct tr{
    ll dp[2][2];
    tr(){
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                dp[i][j]=0;
            }
        }
    }
};
tr emp,t[4*N];
tr mg(const tr&a,const tr &b){
    tr c;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
//            for(int k=0;k<2;k++){
                for(int k=0;k<2;k++){
                    umax(c.dp[i][k],a.dp[i][j]+b.dp[j][k]);
                }
            }
    }
    return c;
}
void upd(int id,ll x,int v,int l,int r){
    if(l==r){
        tr c;
        int ty=(x<0?0:1);
        c.dp[ty][ty]=abs(x);
        c.dp[ty^1][ty^1]=0;
        t[v]=c;
        return;
    }
    int m=(l+r)>>1;
    if(m>=id) upd(id,x,2*v,l,m);
    else upd(id,x,2*v+1,m+1,r);
    t[v]=mg(t[2*v],t[2*v+1]);
}
ll b[N];
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    vec<int>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
//    upd(1,0,1,2,n);
    for(int i=2;i<=n;i++){
        b[i]=a[i]-a[i-1];
        upd(i,b[i],1,2,n);
    }
    while(q--){
        int l,r,x;
        cin>>l>>r>>x;
        if(r+1<=n){
            b[r+1]-=x;
            upd(r+1,b[r+1],1,2,n);
        }
        if(l!=1){
            b[l]+=x;
            upd(l,b[l],1,2,n);
        }

        tr c=t[1];
        ll mx=-inf;
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                umax(mx,c.dp[i][j]);
            }
        }
        cout<<mx<<endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25264 KB Output is correct
2 Correct 15 ms 25340 KB Output is correct
3 Correct 15 ms 25292 KB Output is correct
4 Correct 13 ms 25304 KB Output is correct
5 Correct 13 ms 25376 KB Output is correct
6 Correct 13 ms 25380 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25264 KB Output is correct
2 Correct 15 ms 25340 KB Output is correct
3 Correct 15 ms 25292 KB Output is correct
4 Correct 13 ms 25304 KB Output is correct
5 Correct 13 ms 25376 KB Output is correct
6 Correct 13 ms 25380 KB Output is correct
7 Correct 18 ms 25420 KB Output is correct
8 Correct 17 ms 25328 KB Output is correct
9 Correct 18 ms 25384 KB Output is correct
10 Correct 17 ms 25420 KB Output is correct
11 Correct 16 ms 25432 KB Output is correct
12 Correct 19 ms 25448 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25264 KB Output is correct
2 Correct 15 ms 25340 KB Output is correct
3 Correct 15 ms 25292 KB Output is correct
4 Correct 13 ms 25304 KB Output is correct
5 Correct 13 ms 25376 KB Output is correct
6 Correct 13 ms 25380 KB Output is correct
7 Correct 18 ms 25420 KB Output is correct
8 Correct 17 ms 25328 KB Output is correct
9 Correct 18 ms 25384 KB Output is correct
10 Correct 17 ms 25420 KB Output is correct
11 Correct 16 ms 25432 KB Output is correct
12 Correct 19 ms 25448 KB Output is correct
13 Correct 547 ms 30468 KB Output is correct
14 Correct 537 ms 30516 KB Output is correct
15 Correct 550 ms 30704 KB Output is correct
16 Correct 574 ms 30536 KB Output is correct
17 Correct 548 ms 30608 KB Output is correct
18 Correct 562 ms 30708 KB Output is correct