oj.uz

답안 #442021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442021 2021-07-06T19:08:47 Z keta_tsimakuridze Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
 1 ms 332 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,tree[4*N][2][2],a[N],x[N],n,q;
void update(int u,int ind,int l,int r,int val) {
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[u][0][0] = 0;
		tree[u][1][1] = abs(val);
		return;
	}
	int mid = (l+r)/2;
	update(2*u,ind,l,mid,val);
	update(2*u+1,ind,mid+1,r,val);
	for(int i=0;i<2;i++) {
		for(int j=0;j<2;j++){ tree[u][i][j] = 0;
			for(int k=0;k<2;k++) {
				for(int c=0;c<2;c++) {
					if(k==1 && c==1 && x[mid]*x[mid+1]<0) continue;
					tree[u][i][j] = max(tree[2*u][i][k] + tree[2*u+1][c][j], tree[u][i][j]);
				}
			}
		}
	}
}
 main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin >> a[i];
		if(i-1) update(1,i,1,n,a[i]-a[i-1]);
		x[i] = a[i] - a[i-1];
	}
	while(q--) {
		int l,r,val;
		cin>>l>>r>>val;
		x[l] += val;
		x[r+1] += -val;
		if(l-1) update(1,l,1,n,x[l]);
		update(1,r+1,1,n,x[r+1]);
		cout<<max(max(tree[1][1][1],tree[1][0][0]),max(tree[1][1][0],tree[1][0][1]))<<"\n";
	}
}

Compilation message

Main.cpp:29:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 |  main(){
      |  ^~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -