Submission #1313240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313240		hgia	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	591 ms	22828 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,q;
int a[N],d[N];
int dp[N*4][2][2];
void mergee(int id,int l,int r)
{
  int mid=l+r>>1;
  int left=id*2;
  int right=id*2+1;
  for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
    {
      dp[id][i][j]=-1e18;
      for(int x=0;x<2;x++)
        for(int y=0;y<2;y++)
        {
          if(x==1&&y==1&&d[mid]*d[mid+1]<0)continue;
          dp[id][i][j]=max(dp[id][i][j],dp[left][i][x]+dp[right][y][j]);
        }
    }
}
void update(int id,int l,int r,int pos,int val)
{
  if(pos<l||pos>r)return ;
  if(l==r)
  {
    dp[id][0][0]=0;
    dp[id][1][1]=val;
    dp[id][0][1]=dp[id][1][0]=-1e18;
    return;
  }
  int mid=l+r>>1;
  update(id*2,l,mid,pos,val);
  update(id*2+1,mid+1,r,pos,val);
  mergee(id,l,r);
}
void de(int id,int l,int r)
{
  int mid=l+r>>1;
  cout<<l<<" "<<r<<" "<<dp[id][1][1]<<endl;
  if(l==r)return ;
  de(id*2,l,mid);
  de(id*2+1,mid+1,r);
}
signed main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>q;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<n;i++)
  {
    d[i]=a[i+1]-a[i];
    update(1,1,n-1,i,abs(d[i]));
  }
  // cout<<dp[1][1][1]<<endl;
  for(int i=1;i<=q;i++)
  {
    int l,r,val;
    cin>>l>>r>>val;
    l--;
    // cout<<l<<" "<<r<<endl;
    if(l!=0)
    {
      d[l]+=val;
      update(1,1,n-1,l,abs(d[l]));
      
    }
    if(r!=n)
    {
      d[r]-=val;
      update(1,1,n-1,r,abs(d[r]));
    }
    // cout<<l<<" "<<r<<endl;
    cout<<max({dp[1][1][1],dp[1][1][0],dp[1][0][1],dp[1][0][0]})<<endl;
  }
  // de(1,1,n-1);
  return 0;
}

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