답안 #643554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643554 2022-09-22T12:29:35 Z rsjw Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
268 ms 524288 KB
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int arr[N],a[N];
int n;

int sum[N][2][2];
void chmax(int &var,int v) {
	if(v>var) var=v;
}
void pushup(int rt,bool mixable){
	int i,j,_i,_j;
	for(i=0;i<2;i++) {
		for(j=0;j<2;j++) {
			sum[rt][i][j]=0;
			for(_i=0;_i<2;_i++) {
				for(_j=0;_j<2;_j++) {
					if(_i&&_j&&0==mixable) continue;
					chmax(sum[rt][i][j],sum[rt<<1][i][_i]+sum[rt<<1|1][_j][j]);
				}
			}		
		}
	}
}
void build(int l=1,int r=n,int rt=1) {
	if(l==r) {
		sum[rt][1][1]=abs(a[l]);
		return ;
	}
	int m=(l+r)>>1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);
	pushup(rt,a[m]*a[m+1]>=0);
}
void update(int x,int I,int l=1,int r=n,int rt=1) {
	if(l==r) {
		sum[rt][1][1]=abs(I);
		return ;
	}
	int m=(l+r)>>1;
	if(x<=m) update(x,I,l,m,rt<<1);
	else update(x,I,m+1,r,rt<<1|1);
	pushup(rt,a[m]*a[m+1]>=0);
}
int main() {
	freopen("1.in","r",stdin);
	int q,i,l,r,x;
	cin>>n>>q;
	for(i=1;i<=n;i++) cin>>arr[i];
	for(i=1;i<n;i++) a[i]=arr[i+1]-arr[i];
	n--;
	build();
	int j,_i,_j,ans=0;
	while(q--) {
		cin>>l>>r>>x;
		if(l-1>0) {
			a[l-1]+=x;
			update(l-1,a[l-1]);
		}
		if(r<=n) {
			a[r]-=x;
			update(r,a[r]);
		}
		ans=0;
		for(i=0;i<2;i++)
			for(j=0;j<2;j++) 
				ans=max(ans,sum[1][i][j]);
		cout<<ans<<endl;
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:53:8: warning: unused variable '_i' [-Wunused-variable]
   53 |  int j,_i,_j,ans=0;
      |        ^~
Main.cpp:53:11: warning: unused variable '_j' [-Wunused-variable]
   53 |  int j,_i,_j,ans=0;
      |           ^~
Main.cpp:46:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  freopen("1.in","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 268 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 268 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 268 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -