Submission #46662

#	Time	Username	Problem	Language	Result	Execution time	Memory
46662		maksim_gaponov	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	183 ms	7632 KiB

foehn_phenomena

#define _CRT_SECURE_NO_WARNINGS
#ifdef KEK
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

void openFiles() {
#ifdef KEK
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

const int MAXN = 200000 + 10;
ll a[MAXN];
int n, q, s_up, s_down;
ll delta[MAXN];

int sign(ll f) {
	return (f >= 0);
}

int main() {
	openFiles();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q >> s_up >> s_down;
    n++;
	for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
	ll up_cnt = 0, down_cnt = 0;
	for (int i = 1; i < n; i++) {
        delta[i] = a[i] - a[i - 1];
		if (a[i] > a[i - 1]) {
			up_cnt += delta[i];
		}
		else {
			down_cnt += -delta[i];
		}
	}
	for (int j = 0; j < q; j++) {
		int l, r;
		ll x;
		cin >> l >> r >> x;
		ll left_dist = delta[l];
		ll right_dist = delta[r + 1];
        delta[l] += x;
        delta[r + 1] -= x;
		if (sign(delta[l]) == sign(left_dist)) {
			if (sign(left_dist) == 1) {
				up_cnt += x;
			}
			else {
				down_cnt -= x;
			}
		}
		else {
			if (sign(left_dist) == 1) {
				up_cnt -= left_dist;
				down_cnt += -delta[l];
			}
			else {
				down_cnt -= -left_dist;
				up_cnt += delta[l];
			}
		}
		if (r != n - 1) {
			if (sign(delta[r + 1]) == sign(right_dist)) {
				if (sign(right_dist) == 1) {
					up_cnt -= x;
				}
				else {
					down_cnt += x;
				}
			}
			else {
				if (sign(right_dist) == 1) {
					up_cnt -= right_dist;
					down_cnt += -delta[r + 1];
				}
				else {
					down_cnt -= -right_dist;
					up_cnt += delta[r + 1];
				}
			}
		}
		ll res = down_cnt * s_down - up_cnt * s_up;
		cout << res << "\n";
	}
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60