Submission #480054

#	Time	Username	Problem	Language	Result	Execution time	Memory
480054		David_M	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	16 ms	23872 KiB

Main

#include <bits/stdc++.h>
#define LL long long
#define int LL
#define F first
#define S second
#define FF F.F
#define FS F.S
#define SF S.F
#define SS S.S
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pb push_back
using namespace std;
const LL N=1000006, INF=1e18, P=998244353;

LL q=1, n, m, x, y, z, l, r, val, k, lazy[N], ans, o, u, Ans[N];
vector <pii> v[N], V;
string s;
pair<pair<pii,pii>,pii> T[N];

void push(int v){
	T[v].FF.F+=lazy[v];
	T[v].FS.F+=lazy[v];
	lazy[v<<1]+=lazy[v];
	lazy[v<<1|1]+=lazy[v];
	lazy[v]=0;
}

void upd(int L=1, int R=n, int v=1){
	
	if(l<R)push(v);
	
	if(R<l || L>r)return;
	if(L>=l && R<=r){
		lazy[v]+=val;
		if(L==R){
			T[v].FF.S=T[v].FS.S=L;
			T[v].FF.F+=lazy[v];
			T[v].FS.F+=lazy[v];
			lazy[v]=0;
		}
		return;
	}
	int mid=L+R>>1;
	upd(L,mid,v<<1);
	upd(mid+1,R,v<<1|1);
	
	push(v<<1);
	push(v<<1|1);
	
	T[v]={{max(T[v<<1].FF,T[v<<1|1].FF),
		   min(T[v<<1].FS,T[v<<1|1].FS)},
		  {max(T[v<<1].FF.F-T[v<<1|1].FS.F, max(T[v<<1].SF, T[v<<1|1].SF)),
		   max(T[v<<1|1].FS.F-T[v<<1].FF.F, max(T[v<<1].SS, T[v<<1|1].SS))}};
}

pair<int, int> get_max(int L=1, int R=n, int v=1){
	
	push(v);
	if(R<l || L>r)return {-1,-1};
	if(L>=l && R<=r)return T[v].FF;
	int mid=L+R>>1;
	return max(get_max(L, mid, v<<1), get_max(mid+1, R, v<<1|1));
}


pair<int, int> get_min(int L=1, int R=n, int v=1){
	
	push(v);
	if(R<l || L>r)return {INF,-1};
	if(L>=l && R<=r)return T[v].FS;
	int mid=L+R>>1;
	return min(get_min(L, mid, v<<1), get_min(mid+1, R, v<<1|1));
}

int get1(int ll, int rr, int L=1, int R=n, int v=1){
	
	push(v);
	if(R<ll||L>rr)return -1;
	if(L>=ll && R<=rr)return T[v].SF;
	int mid=L+R>>1;
	l=L;r=mid+0; int mn=get_min().F;
	l=mid+1;r=R; int mx=get_max().F;
	return max(mx-mn,max(get1(ll,rr,L,mid,v<<1),get1(ll,rr,mid+1,R,v<<1|1)));

}

int get2(int ll, int rr, int L=1, int R=n, int v=1){
	
	push(v);
	if(R<ll||L>rr)return -1;
	if(L>=ll && R<=rr)return T[v].SS;
	int mid=L+R>>1;
	l=mid+1;r=R; int mn=get_min().F;
	l=L;r=mid+0; int mx=get_max().F;
	return max(mx-mn,max(get2(ll,rr,L,mid,v<<1),get2(ll,rr,mid+1,R,v<<1|1)));
	
}

main(){ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>q;
	for (int i=1; i<=n; i++)
		cin>>val,l=r=i,upd();
	
//	cout<<"AAA"<<get_max().F<<endl;
	while(q--){
		o=0;
		cin>>l>>r>>val;
		upd();
		
		auto [mx,i]=T[1].FF;
		auto [mn,j]=T[1].FS;
//		cout<<mx<<" "<<mn<<" "<<i<<" "<<j<<endl;
		int e, mn1, mn2, mn3, mx1, mx2, mx3;
		e=mx-mn;
		if(i>j)swap(i,j),o=1,swap(mx,mn);
		ans=((o)?(get1(i+1,j-1)):(get2(i+1,j-1)));
		
		l=1;r=i-1;  mx1=get_max().F;mn1=get_min().F;
		l=i+1;r=j-1;mx2=get_max().F;mn2=get_min().F;
		l=j+1;r=n;  mx3=get_max().F;mn3=get_min().F;
		
		ans=max(ans,
				max(max((mx1-mn1)+e, max(mx-mn1, mx1-mx)+max(max(mx2,mx3)-mn, mn-min(mn2, mn3))),
					max(e+(mx3-mn3), max(mn-mn3, mx3-mn)+max(max(mx1,mx2)-mx, mx-min(mn1, mn2)))));
		cout<<ans<<'\n';
	}
	
}

Compilation message (stderr)

Main.cpp: In function 'void upd(long long int, long long int, long long int)':
Main.cpp:44:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |  int mid=L+R>>1;
      |          ~^~
Main.cpp: In function 'std::pair<long long int, long long int> get_max(long long int, long long int, long long int)':
Main.cpp:62:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |  int mid=L+R>>1;
      |          ~^~
Main.cpp: In function 'std::pair<long long int, long long int> get_min(long long int, long long int, long long int)':
Main.cpp:72:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |  int mid=L+R>>1;
      |          ~^~
Main.cpp: In function 'long long int get1(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:81:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |  int mid=L+R>>1;
      |          ~^~
Main.cpp: In function 'long long int get2(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:93:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |  int mid=L+R>>1;
      |          ~^~
Main.cpp: At global scope:
Main.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main(){ios_base::sync_with_stdio(false), cin.tie(0);
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:112:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |   auto [mx,i]=T[1].FF;
      |        ^
Main.cpp:113:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |   auto [mn,j]=T[1].FS;
      |        ^

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