oj.uz

답안 #440221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440221 2021-07-01T19:08:35 Z leaked Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
 15 ms 25340 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]=-inf;
            }
        }
    }
};
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 t=0;t<2;t++){
                    if(to[i][j][t][k].f!=-1){
                        pii w=to[i][j][t][k];
                        umax(c.dp[w.f][w.s],a.dp[i][j]+b.dp[t][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);
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                for(int t=0;t<2;t++){
                    to[i][j][k][t]={-1,-1};
                }
            }
            emp.dp[i][j]=0;
        }
    }
    to[0][1][1][1]={0,1};
    //to[0][0][1][1]={0,1};
    to[0][0][0][1]={0,1};

    to[1][1][1][1]={1,1};

    to[0][0][0][0]={0,0};

    to[1][0][0][0]={1,0};
   // to[1][1][0][0]={1,0};
    to[1][1][1][0]={1,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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 25340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 25340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 25340 KB Output isn't correct
2 Halted 0 ms 0 KB -