oj.uz

Submission #442023

# Submission time Handle Problem Language Result Execution time Memory
442023 2021-07-06T19:25:01 Z keta_tsimakuridze Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1547 ms 22940 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 && min(x[mid],x[mid+1])<0 && max(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];
		x[i] = a[i] - a[i-1];
		if(i-1) update(1,i,1,n,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]))<<endl;
	}
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 16 ms 624 KB Output is correct
8 Correct 16 ms 656 KB Output is correct
9 Correct 16 ms 588 KB Output is correct
10 Correct 16 ms 588 KB Output is correct
11 Correct 18 ms 648 KB Output is correct
12 Correct 17 ms 632 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 16 ms 624 KB Output is correct
8 Correct 16 ms 656 KB Output is correct
9 Correct 16 ms 588 KB Output is correct
10 Correct 16 ms 588 KB Output is correct
11 Correct 18 ms 648 KB Output is correct
12 Correct 17 ms 632 KB Output is correct
13 Correct 1518 ms 22776 KB Output is correct
14 Correct 1524 ms 22940 KB Output is correct
15 Correct 1547 ms 22844 KB Output is correct
16 Correct 1518 ms 22748 KB Output is correct
17 Correct 1505 ms 22708 KB Output is correct
18 Correct 1499 ms 22764 KB Output is correct