Submission #1011961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011961		vantam	Sjeckanje (COCI21_sjeckanje)	C++17	15 / 110	2040 ms	604 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=1005 ;
long long i,j,n,q,type,l,r,x,ma,mi,lt,rt;
long long a[200005],dp[200005] ;
long long si[4*N],sa[4*N],st[4*N],s[4*N],lzi[4*N],lza[4*N];
pair<int,long long> lz[4*N];
int fi[N], fa[N] ;
deque<int> qq ;
void up(int id, int l, int r, int u, long long x){
    if(r<u ||  u<l) return ;
    if(l==r){
        s[id]=x ;
        return ;
    }
    int mid=(l+r)/2 ;
    up(2*id,l,mid,u,x) ;
    up(2*id+1,mid+1,r,u,x) ;
    s[id]=max(s[2*id], s[2*id+1]) ;
    return ;
}
void fixi(int id, int l, int r){
    if(lzi[id]==ma) return ;
    si[id]=s[id]-lzi[id] ;
    if(l!=r){
        lzi[2*id]=lzi[id] ;
        lzi[2*id+1]=lzi[id] ;
    }
    lzi[id]=ma ;
    return ;
}
void upi(int id, int l, int r, int u, int v, long long x){
    fixi(id,l,r) ;
    if(r<u || v<l) return ;
    if(u<=l && r<=v){
        lzi[id]=x ;
        fixi(id,l,r) ;
        return ;
    }
    int mid=(l+r)/2 ;
    upi(2*id,l,mid,u,v,x) ;
    upi(2*id+1,mid+1,r,u,v,x) ;
    si[id]=max(si[2*id], si[2*id+1]) ;
    return ;
}
void fixa(int id, int l, int r){
    if(lza[id]==ma) return ;
    sa[id]=s[id]+lza[id] ;
    if(l!=r){
        lza[2*id]=lza[id] ;
        lza[2*id+1]=lza[id] ;
    }
    lza[id]=ma ;
    return ;
}
void upa(int id, int l, int r, int u, int v, long long x){
    fixa(id,l,r) ;
    if(r<u || v<l) return ;
    if(u<=l && r<=v){
        lza[id]=x ;
        fixa(id,l,r) ;
        return ;
    }
    int mid=(l+r)/2 ;
    upa(2*id,l,mid,u,v,x) ;
    upa(2*id+1,mid+1,r,u,v,x) ;
    sa[id]=max(sa[2*id], sa[2*id+1]) ;
    return ;
}
void fixx(int id,int l, int r,int u, int v,int ii){
    if(ii==1) fixa(id,l,r) ;
    else fixi(id,l,r) ;
    if(l==u && r==v) return ;
    int mid=(l+r)/2 ;
    if(v<=mid){
        fixx(2*id,l,mid,u,v,ii) ;
    }else{
        fixx(2*id+1,mid+1,r,u,v,ii) ;
    }
}
void fix(int id,int l, int r){
    if(lz[id].second==ma) return ;
    if(lz[id].first==1){
        fixx(1,1,n,l,r,1) ;
        st[id]=sa[id]-lz[id].second ;
    }else{
        fixx(1,1,n,l,r,2) ;
        st[id]=si[id]+lz[id].second;
    }
    if(l!=r){
        lz[2*id]=lz[id] ;
        lz[2*id+1]=lz[id] ;
    }
    lz[id].second=ma ;
    return ;
}
void upd(int id, int l, int r, int u, int v,int ii, long long x){
    fix(id,l,r) ;
    if(r<u || v<l) return ;
    if(u<=l && r<=v){
        lz[id]={ii,x} ;
        fix(id,l,r) ;
        return ;
    }
    int mid=(l+r)/2 ;
    upd(2*id,l,mid,u,v,ii,x) ;
    upd(2*id+1,mid+1,r,u,v,ii,x) ;
    st[id]=max(st[2*id], st[2*id+1]) ;
    return ;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    #define NAME "test"
    if(fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    cin >> n >> q;
    for(i=1;i<=n;i++) cin >> a[i] ;
    //if(n*q<=1000000){
        while(q--){
            //cin >> type ;
           // if(type==1){
                cin >> l >> r >> x ;
                for(i=l;i<=r;i++) a[i]+=x ;
            //}else{
              //  if(n*n*q<=10000000){
                    dp[0]=0 ;
                    for(i=1;i<=n;i++){
                        ma=a[i];
                        mi=a[i];
                        dp[i]=-1e18;
                        for(j=i;j>=1;j--){
                            ma=max(ma,a[j]) ;
                            mi=min(mi,a[j]) ;
                            dp[i]=max(dp[i], dp[j-1]+ma-mi) ;
                        }
                    }
                    cout << dp[n] << '\n' ;
//                }else{
//                    ma=-2000000000000000 ;
//                    for(i=0;i<=4*n;i++){
//                        lz[i].second=ma ;
//                        si[i]=ma ;
//                        sa[i]=ma;
//                        st[i]=ma;
//                        s[i]=ma;
//                        lzi[i]=ma;
//                        lza[i]=ma;
//                    }
//                    qq.clear() ;
//                    for(i=1;i<=n;i++){
//                        while(!qq.empty() && a[qq.front()]<=a[i]) qq.pop_front() ;
//                        if(!qq.empty()) fa[i]=qq.front()+1 ;
//                        else fa[i]=i ;
//                        qq.push_back(i) ;
//                    }
//                    qq.clear() ;
//                    for(i=1;i<=n;i++){
//                        while(!qq.empty() && a[qq.front()]>=a[i]) qq.pop_front() ;
//                        if(!qq.empty()) fi[i]=qq.front()+1 ;
//                        else fi[i]=i ;
//                        qq.push_back(i) ;
//                    }
//                    dp[0]=0 ;
//                    dp[1]=0 ;
//                    up(1,0,n-1,0,0) ;
//                    up(1,0,n-1,1,0) ;
//                    upi(1,1,n,1,1,a[1]) ;
//                    upa(1,1,n,1,1,a[1]) ;
//                    upd(1,1,n,1,1,1,a[1]) ;
//                    for(i=2;i<=n;i++){
//                        if(fa[i]!=fi[i]){
//                            if(fa[i]<fi[i]){
//                                lt=fa[i] ;
//                                rt=fi[i] ;
//                                upa(1,1,n,lt,rt-1,a[i]) ;
//                                upd(1,1,n,lt,rt-1,2,a[i]) ;
//                            }else{
//                                lt=fi[i] ;
//                                rt=fa[i] ;
//                                upi(1,1,n,lt,rt-1,a[i]) ;
//                                upd(1,1,n,lt,rt-1,1,a[i]) ;
//                            }
//                        }
//                        fix(1,1,n) ;
//                        dp[i]=st[1] ;
//                        up(1,0,n-1,i,dp[i]) ;
//                    }
//                    cout << dp[n] << '\n' ;
//                }
            }
       // }
   // }
    return 0;
}
/*
4 7
-1 3 -6 8
1 4 4 2
2
1 4 4 3
2
1 1 2 -1
1 1 2 -4
2
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55