제출 #1141600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141600		sayan	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1042 ms	456 KiB

Main

#include <bits/stdc++.h>
#define Sayan ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define sz() size()
#define F first
#define S second
#define pb push_back
#define yes cout << "YES\n"
#define no cout << "NO\n"
using namespace std ;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const ll N = 200+5;
const ll inf = 1e18;
const int mod = 1e9+7; // 998244353;
//////////////////////////////////////////////////////
ll TEST=0;
ll n , q;
map<ll,ll>mp;
ll a[N] , dp[N] , lz[N*4];
pair<ll , ll> t[N*4];
//////////////////////////////////////////////////////
struct delai{
	// ll l,r;
};
void push(ll tl,ll tr,ll v){
	t[v+v].F+=lz[v];
	t[v+v+1].F+=lz[v];
	t[v+v].S+=lz[v];
	t[v+v+1].S+=lz[v];
	lz[v+v]+=lz[v];
	lz[v+v+1]+=lz[v];
	lz[v]=0;
}
void build(ll v=1,ll tl=1,ll tr=n){
	if(tl==tr){
		t[v]={a[tl],a[tl]};
		return ;
	}
	ll tm=(tl+tr)/2;
	build(v+v,tl,tm);
	build(v+v+1,tm+1,tr);
	t[v].F=min(t[v+v].F,t[v+v+1].F);
	t[v].S=max(t[v+v].S,t[v+v+1].S);
}
ll get(ll l,ll r,ll ok,ll v=1,ll tl=1,ll tr=n){
	push(tl,tr,v);
	if(l<=tl && tr<=r){
		if(ok==1)return t[v].F;
		else return t[v].S;
	}
	if(tr<l or r<tl){
		if(ok==1)return inf;
		else return 0;
	}
	ll tm=(tl+tr)/2;
	if(ok==1)return min(get(l,r,ok,v+v,tl,tm),get(l,r,ok,v+v+1,tm+1,tr));
	else return max(get(l,r,ok,v+v,tl,tm),get(l,r,ok,v+v+1,tm+1,tr));
}
void upd(ll l,ll r,ll sum,ll v=1,ll tl=1,ll tr=n){
	push(tl,tr,v);
	if(l<=tl && tr<=r){
		t[v].F+=sum;
		t[v].S+=sum;
		lz[v]+=sum;
		return;
	}
	if(tr<l or r<tl){
		return ;
	}
	ll tm=(tl+tr)/2;
	upd(l,r,sum,v+v,tl,tm);
	upd(l,r,sum,v+v+1,tm+1,tr);
	t[v].F=min(t[v+v].F,t[v+v+1].F);
	t[v].S=max(t[v+v].S,t[v+v+1].S);
}
//////////////////////////////////////////////////////
void solve(){
	cin >> n >> q;
	for(ll i = 1 ; i <= n ; i++){
		cin >> a[i];
	}
	for(ll i=1;i<=n;i++)dp[i]=-inf;
	build();
	while(q--){
		ll l,r,sum;
		cin>>l>>r>>sum;
		upd(l,r,sum);
		ll ans=0;
		for(ll i=1;i<=n;i++)dp[i]=-inf;
		for(ll i=1;i<=n;i++){
			for(ll j=i;j>=1;j--){
				ll mn=get(j,i,1);
				ll mx=get(j,i,2);
				dp[i]=max(dp[i],mx-mn+dp[j-1]);
			}
			ans=max(ans,dp[i]);
		}
		cout<<ans<<" ";
	}
}
signed main () {
	Sayan;
	ll t=1;
	if(TEST){
		cin>>t;	
	}
	while(t--)solve();
}

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