Submission #1261685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261685		KALARRY	Sjeckanje (COCI21_sjeckanje)	C++20	15 / 110	2092 ms	1040 KiB

Main

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const long long INF = 1e15;

long long N,Q,a[200005],dp[200005],l_big[200005],l_small[200005];

struct Node
{
    long long max_dp = -INF,val_max=-INF,val_min=-INF,lazy_max=0,lazy_min=0;
}st[800005];

void propagate(int v,int start,int end);

void update_max(int l,int r,long long val,int v = 1,int start = 1,int end = N)
{
    if(start==l && end==r)
    {
        st[v].val_max = val + st[v].max_dp;
        st[v].lazy_max = val;
        return;
    }
    propagate(v,start,end);
    int mid = (start + end)/2;
    if(r <= mid)
        update_max(l,r,val,2*v,start,mid);
    else if(l > mid)
        update_max(l,r,val,2*v+1,mid+1,end);
    else
    {
        update_max(l,mid,val,2*v,start,mid);
        update_max(mid+1,r,val,2*v+1,mid+1,end);
    }
    st[v].val_max = max(st[2*v].val_max,st[2*v+1].val_max);
}

void update_min(int l,int r,long long val,int v = 1,int start = 1,int end = N)
{
    if(start==l && end==r)
    {
        st[v].val_min = st[v].max_dp - val;
        st[v].lazy_min = val;
        return;
    }
    propagate(v,start,end);
    int mid = (start + end)/2;
    if(r <= mid)
        update_min(l,r,val,2*v,start,mid);
    else if(l > mid)
        update_min(l,r,val,2*v+1,mid+1,end);
    else
    {
        update_min(l,mid,val,2*v,start,mid);
        update_min(mid+1,r,val,2*v+1,mid+1,end);
    }
    st[v].val_min = max(st[2*v].val_min,st[2*v+1].val_min);
}

void propagate(int v,int start,int end)
{
    int mid = (start + end)/2;
    if(st[v].lazy_max)
    {
        update_max(start,mid,st[v].lazy_max,2*v,start,mid);
        update_max(mid+1,end,st[v].lazy_max,2*v+1,mid+1,end);
        st[v].lazy_max = 0;
    }
    if(st[v].lazy_min)
    {
        update_min(start,mid,st[v].lazy_min,2*v,start,mid);
        update_min(mid+1,end,st[v].lazy_min,2*v+1,mid+1,end);
        st[v].lazy_min = 0;
    }
}

void update_dp(int pos,int v = 1,int start = 1,int end = N)
{
    if(start==end)
    {
        st[v].max_dp = dp[pos-1];
        st[v].val_max = dp[pos-1] + a[pos];
        st[v].val_min = dp[pos-1] - a[pos];
        return;
    }
    propagate(v,start,end);
    int mid = (start + end)/2;
    if(pos <= mid)
        update_dp(pos,2*v,start,mid);
    else
        update_dp(pos,2*v+1,mid+1,end);
    st[v].max_dp = max(st[2*v].max_dp,st[2*v+1].max_dp);
    st[v].val_max = max(st[2*v].val_max,st[2*v+1].val_max);
    st[v].val_min = max(st[2*v].val_min,st[2*v+1].val_min);
}

stack<pair<long long,int>> ord;
long long calc()
{
    ord.push({-INF,0});
    for(int i = 1 ; i <= N ; i++)
    {
        while(ord.top().first > a[i])
            ord.pop();
        l_small[i] = ord.top().second+1;
        ord.push({a[i],i});
    }
    while(!ord.empty())
        ord.pop();
    ord.push({INF,0});
    for(int i = 1 ; i <= N ; i++)
    {
        while(ord.top().first < a[i])
            ord.pop();
        l_big[i] = ord.top().second+1;
        ord.push({a[i],i});
    }
    while(!ord.empty())
        ord.pop();
    long long ret = 0;
    for(int v = 1 ; v<= 4*N ; v++)
    {
        st[v].max_dp = -INF;
        st[v].val_max=-INF;
        st[v].val_min=-INF;
        st[v].lazy_max=0;
        st[v].lazy_min=0;
    }
    for(int i = 1 ; i <= N ; i++)
    {
        update_dp(i);
        update_max(l_big[i],i,a[i]);
        update_min(l_small[i],i,a[i]);
        pair<long long,long long> res = {st[1].val_max,st[1].val_min};
        dp[i] = max(res.first - a[i],res.second + a[i]);
    }
    return dp[N];
}

int main()
{
    scanf("%lld%lld",&N,&Q);
    for(int i = 1 ; i <= N ; i++)
    scanf("%lld",&a[i]);
    for(int l,r,x,i = 1 ; i <= Q ; i++)
    {
        scanf("%d%d%d",&l,&r,&x);
        for(int j = l ; j <= r ; j++)
            a[j] += x;
        printf("%lld\n",calc());
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |     scanf("%lld%lld",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     scanf("%lld",&a[i]);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         scanf("%d%d%d",&l,&r,&x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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