제출 #1313231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313231		hgia	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1 ms	332 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;
  dp[id][1][1]=max({(dp[left][1][1]+dp[right][1][1])*(d[mid]*d[mid+1]>=0),dp[left][1][0]+dp[right][0][1]
                    ,dp[left][1][1]+dp[right][0][1],dp[left][1][0]+dp[right][1][1]});
  dp[id][0][0]=max({(dp[left][0][1]+dp[right][1][0])*(d[mid]*d[mid+1]>=0),dp[left][0][0]+dp[right][0][0]
                    ,dp[left][0][1]+dp[right][0][0],dp[left][0][0]+dp[right][1][0]});
  dp[id][1][0]=max({(dp[left][1][1]+dp[right][1][0])*(d[mid]*d[mid+1]>=0),dp[left][1][0]+dp[right][0][0]
                    ,dp[left][1][1]+dp[right][0][0],dp[left][1][0]+dp[right][1][0]});
  dp[id][0][1]=max({(dp[left][0][1]+dp[right][1][1])*(d[mid]*d[mid+1]>=0),dp[left][0][0]+dp[right][0][1]
                    ,dp[left][0][1]+dp[right][0][1],dp[left][0][0]+dp[right][1][1]});
}
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]=-1e9;
    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,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;
      int tmp=d[l];
      if(tmp<0)tmp*=-1;
      update(1,1,n-1,l,tmp);
      
    }
    if(r!=n)
    {
      d[r]-=val;
      int tmp=d[r];
      if(tmp<0)tmp*=-1;
      update(1,1,n-1,r,tmp);
    }
    // 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: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55