oj.uz

Submission #950040

# Submission time Handle Problem Language Result Execution time Memory
950040 2024-03-20T03:56:20 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 6484 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define mp make_pair
#define ll long long
const ll INF=1e18,N=2e5+5;
void solve(){
	int n,q;cin>>n>>q;
	vector<ll> a(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	vector<ll> dp(n),prv(n);
	while(q--){
		int l,r,x;cin>>l>>r>>x;
		
		for(int i=l;i<=r;i++) a[i]+=x;
		dp[1]=0;
		dp[2]=abs(a[2]-a[1]);
		prv[2]=1;
		for(int i=3;i<=n;i++){
			dp[i]=dp[i-1];
			if((a[i]>=a[i-1]) == (a[i-1]>=a[i-2])) prv[i]=prv[i-1];
			
			else prv[i]=i-1;
			dp[i]=max(dp[i],abs(a[i]-a[prv[i]])+dp[prv[i]-1]);
			dp[i]=max(dp[i],abs(a[i]-a[prv[i]+1])+dp[prv[i]]);
		}
		cout<<dp[n]<<endl;
	}
}
int main(){
	solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 55 ms 760 KB Output is correct
8 Correct 49 ms 616 KB Output is correct
9 Correct 50 ms 588 KB Output is correct
10 Correct 53 ms 600 KB Output is correct
11 Correct 54 ms 600 KB Output is correct
12 Correct 45 ms 612 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 55 ms 760 KB Output is correct
8 Correct 49 ms 616 KB Output is correct
9 Correct 50 ms 588 KB Output is correct
10 Correct 53 ms 600 KB Output is correct
11 Correct 54 ms 600 KB Output is correct
12 Correct 45 ms 612 KB Output is correct
13 Execution timed out 2029 ms 6484 KB Time limit exceeded
14 Halted 0 ms 0 KB -