Submission #162300

#	Time	Username	Problem	Language	Result	Execution time	Memory
162300		kostia244	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	426 ms	11640 KiB

foehn_phenomena

#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vector<ll>>;
const ll mod = 998244353;
using oset = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5 + 33;
struct fenwick {
	int n;
	ll tree[maxn];
	void init(int sz) {
		n = sz;
		memset(tree, 0, sizeof tree);
	}
	void _add(int i, ll x) {
		while (i <= n) {
			tree[i] += x;
			i += i & -i;
		}
	}
	void add(int l, int r, ll x) {
		_add(l, x);
		_add(r + 1, -x);
	}
	ll get(int i) {
		ll res = 0;
		while (i) {
			res += tree[i];
			i -= i & -i;
		}
		return res;
	}
};
ll n, q, s, t;
fenwick f;
ll val(int i) {
	if(i>n) return 0;
	ll diff = f.get(i - 1) - f.get(i);
	if (diff < 0)
		return s * diff;
	return t * diff;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q >> s >> t;
	f.init(n);
	int tmp;
	cin >> tmp;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		f.add(i, i, tmp);
		ans += val(i);
	}
	ll l, r, x;
	while (q--) {
		cin >> l >> r >> x;
		ans -= val(l), ans -= val(r+1);
		f.add(l, r, x);
		ans += val(l), ans += val(r+1);
		cout << ans << "\n";
	}
}

Compilation message (stderr)

foehn_phenomena.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

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