oj.uz

Submission #874360

# Submission time Handle Problem Language Result Execution time Memory
874360 2023-11-16T17:50:34 Z ngjabach Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 661 ms 64056 KB 
// NgJaBach: Forever Meadow <3

#include<bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int ll;
typedef unsigned long long ull;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define bend(a) a.begin(),a.end()
#define rev(x) reverse(bend(x))
#define mset(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=1e18+7;
struct ask{
    int x,y;
    ll z;
};
ll arr[N];
int q,n;
vector<ask>queries;
namespace sub1{
    ll a[205],dp[205],minis[205][205],maxis[205][205];
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            for(int i=x;i<=y;++i) a[i]+=z;
            for(int i=1;i<=n;++i){
                maxis[i][i]=a[i];
                minis[i][i]=a[i];
                for(int j=i+1;j<=n;++j){
                    maxis[i][j]=max(maxis[i][j-1],a[j]);
                    minis[i][j]=min(minis[i][j-1],a[j]);
                }
            }
            dp[0]=0;
            for(int i=1;i<=n;++i){
                dp[i]=-INF;
                for(int j=1;j<=i;++j) dp[i]=max(dp[i],dp[j-1]+maxis[j][i]-minis[j][i]);
            }
            ans.pb(dp[n]);
        }
        return ans;
    }
}
namespace sub2{
    ll a[3005],dp[3005][2],d[3005];
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            for(int i=x;i<=y;++i) a[i]+=z;
            for(int i=1;i<n;++i) d[i]=a[i]-a[i+1];
            dp[0][0]=0; dp[0][1]=0; d[n]=0;
            for(int i=1;i<n;++i){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=max(dp[i-1][0],dp[i-1][1]*(d[i]*d[i-1]>=0))+abs(d[i]);
            }
            ans.pb(max(dp[n-1][0],dp[n-1][1]));
        }
        return ans;
    }
}
namespace sub3{
    ll a[N],d[N],lazy[4*N];
    struct node{
        ll l,r;
        ll F[2][2];
        node(){
            for(int i=0;i<2;++i){
                for(int j=0;j<2;++j){
                    F[i][j]=-INF;
                }
            }
            return;
        }
    }seg[4*N];
    node Combine(node A,node B){
        node C;
        C.l=A.l; C.r=B.r;
        for(int x=0;x<2;++x){
            for(int y=0;y<2;++y){
                for(int u=0;u<2;++u){
                    for(int v=0;v<2;++v){
                        if(A.F[x][y]==-INF or B.F[u][v]==-INF) continue;
                        ll best=A.F[x][y]+B.F[u][v];
                        if(y==u){
                            if(y==0 and A.r<B.l) best+=B.l-A.r;
                            else if(y==1 and A.r>B.l) best+=A.r-B.l;
                        }
                        C.F[x][v]=max(C.F[x][v],best);
                    }
                }
            }
        }
        return C;
    }
    void Build(int x,int L,int R){
        lazy[x]=0;
        if(L==R){
            seg[x].l=seg[x].r=a[L];
            seg[x].F[0][0]=0; seg[x].F[1][1]=0;
            return;
        }
        int mid=(L+R)/2;
        Build(2*x,L,mid);
        Build(2*x+1,mid+1,R);
        seg[x]=Combine(seg[2*x],seg[2*x+1]);
        return;
    }
    void Update_Lazy(int x,int L,int R){
        if(!lazy[x]) return;
        seg[x].l+=lazy[x]; seg[x].r+=lazy[x];
        if(L!=R){
            lazy[2*x]+=lazy[x];
            lazy[2*x+1]+=lazy[x];
        }
        lazy[x]=0;
        return;
    }
    void Update(int x,int L,int R,int lo,int hi,ll val){
        Update_Lazy(x,L,R);
        if(L>hi or R<lo) return;
        else if(L>=lo and R<=hi){
            lazy[x]=val;
            Update_Lazy(x,L,R);
            return;
        }
        int mid=(L+R)/2;
        Update(2*x,L,mid,lo,hi,val);
        Update(2*x+1,mid+1,R,lo,hi,val);
        seg[x]=Combine(seg[2*x],seg[2*x+1]);
        return;
    }
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        Build(1,1,n);
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            Update(1,1,n,x,y,z);
            ll res=-INF;
            for(int i=0;i<2;++i) for(int j=0;j<2;++j) res=max(res,seg[1].F[i][j]);
            ans.pb(res);
        }
        return ans;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//    freopen("RECIPE.inp","r",stdin);
//    freopen("RECIPE.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>arr[i];
    for(int i=0;i<q;++i){
        int x,y,z;
        cin>>x>>y>>z;
        queries.pb({x,y,z});
    }
    vector<ll>ans;
//    if(n<=200 and q<=200) ans=sub1::solve();
//    else if(n<=3000 and q<=3000) 
    ans=sub3::solve();
    for(ll &tmp:ans) cout<<tmp<<endl;
    return 0;
}
/*
==================================+
INPUT:                            |
------------------------------    |

------------------------------    |
==================================+
OUTPUT:                           |
------------------------------    |

------------------------------    |
==================================+
*/

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41560 KB Output is correct
2 Correct 6 ms 41564 KB Output is correct
3 Correct 6 ms 41688 KB Output is correct
4 Correct 6 ms 41560 KB Output is correct
5 Correct 6 ms 41560 KB Output is correct
6 Correct 6 ms 41560 KB Output is correct
7 Correct 13 ms 41820 KB Output is correct
8 Correct 11 ms 41820 KB Output is correct
9 Correct 11 ms 41952 KB Output is correct
10 Correct 11 ms 41820 KB Output is correct
11 Correct 12 ms 41948 KB Output is correct
12 Correct 11 ms 41940 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41560 KB Output is correct
2 Correct 6 ms 41564 KB Output is correct
3 Correct 6 ms 41688 KB Output is correct
4 Correct 6 ms 41560 KB Output is correct
5 Correct 6 ms 41560 KB Output is correct
6 Correct 6 ms 41560 KB Output is correct
7 Correct 13 ms 41820 KB Output is correct
8 Correct 11 ms 41820 KB Output is correct
9 Correct 11 ms 41952 KB Output is correct
10 Correct 11 ms 41820 KB Output is correct
11 Correct 12 ms 41948 KB Output is correct
12 Correct 11 ms 41940 KB Output is correct
13 Correct 661 ms 63208 KB Output is correct
14 Correct 633 ms 63112 KB Output is correct
15 Correct 623 ms 64056 KB Output is correct
16 Correct 620 ms 63420 KB Output is correct
17 Correct 630 ms 62956 KB Output is correct
18 Correct 631 ms 63900 KB Output is correct