Submission #967321

#	Time	Username	Problem	Language	Result	Execution time	Memory
967321		Math4Life2020	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	348 KiB

Main

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
	long long N,Q; cin >> N >> Q;
	long long a[N];
	for (long long i=0;i<N;i++) {
		cin >> a[i];
	}

	//solve:
	for (long long q=0;q<Q;q++) {
		long long l,r,x; cin >> l >> r >> x;
		l--; r--;
		for (long long i=l;i<=r;i++) {
			a[i] += x;
		}
		long long val = 0;
		long long d[N];
		for (long long i=0;i<N;i++) {
			d[i]=0;
		}
		vector<long long> cv;
		for (long long i=1;i<N;i++) {
			val += abs(a[i]-a[i-1]);
			if (i<(N-1)) {
				/*if (!(((a[i-1]<a[i])&&(a[i]<a[i+1]))||((a[i-1]>a[i])&&(a[i]>a[i+1])))) {
					val -= min(abs(a[i]-a[i-1]),abs(a[i]-a[i+1]));
				}*/
				if ((a[i-1]<a[i])&&(a[i]>a[i+1])) {
					d[i]=1;
				} else if ((a[i-1]>a[i])&&(a[i]>a[i+1])) {
					d[i]=-1;
				}
				if ((d[i] != 0)&&(cv.size()==0)) {
					cv.push_back(i-1); cv.push_back(i);
				} else if (d[i] != 0) {
					cv.push_back(i);
				} else if (cv.size()!=0) {
					cv.push_back(i);
					long long K = cv.size();
					long long sn = 0; long long sl = 0;
					for (int j=1;j<K;j++) {
						int d = abs(a[cv[j]]-a[cv[j-1]]);
						long long sn1 = sl;
						long long sl1 = min(sn,sl)+d;
						sn = sn1; sl = sl1;
					}
					val -= min(sl,sn);
					cv.clear();
				}
			}
		}
		cout << val <<"\n";
	}
}

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