Submission #307520

#	Time	Username	Problem	Language	Result	Execution time	Memory
307520		TeaTime	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	133 ms	13176 KiB

foehn_phenomena

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e6 * 2 + 10, INF = 1e9 * 1e9 + 10;

ll check(ll vl, ll s) {
	ll ans = vl - 1;
	ans += (s - 1) / vl;
	return ans;
}

ll get(ll s) {
	ll l = 1, r = s;
	while (r - l > 100000) {
		ll mid = (l + r) / 2;
		ll mid2 = mid + 1;
		if (check(mid, s) > check(mid2, s)) {
			l = mid - 1;
		}
		else {
			r = mid2 + 1;
		}
	}

	ll ans = INF;
	for (int i = l; i <= r; i++) {
		ans = min(ans, check(i, s));
	}

	return ans;
}
int main()
{
	fastInp;

	ll n, q, s, t;
	cin >> n >> q >> s >> t;
	n++;
	vector<ll> vec(n), vec2(n - 1);

	for (auto &cur : vec) cin >> cur;

	ll d = 0;
	for (int i = 1; i < n; i++) {
		vec2[i - 1] = vec[i] - vec[i - 1];
		if (vec[i] < vec[i - 1]) {
			d += abs(vec[i] - vec[i - 1]) * t;
		}
		else {
			d -= abs(vec[i] - vec[i - 1]) * s;
		}
	}

	while (q--) {
		ll ind, ind2, vl;
		cin >> ind >> ind2 >> vl;

		ll i = ind - 1;
		if (vec2[i] < 0) {
			d -= abs(vec2[i]) * t;
		}
		else {
			d += vec2[i] * s;
		}

		vec2[i] += vl;

		if (vec2[i] < 0) {
			d += abs(vec2[i]) * t;
		}
		else {
			d -= vec2[i] * s;
		}

		if (ind2 != n - 1) {
			ll i = ind2;
			if (vec2[i] < 0) {
				d -= abs(vec2[i]) * t;
			}
			else {
				d += vec2[i] * s;
			}

			vec2[i] -= vl;

			if (vec2[i] < 0) {
				d += abs(vec2[i]) * t;
			}
			else {
				d -= vec2[i] * s;
			}
		}
		cout << d << "\n";
	}

	return 0;
}

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