Submission #337125

#	Time	Username	Problem	Language	Result	Execution time	Memory
337125		deadeye	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	262 ms	14740 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;

#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 69
#endif
template <typename Arg>
void __f(string name, Arg arg) {
	cerr << name << " = " << arg << endl;
}
template <typename Head, typename... Tail>
void __f(string names, Head head, Tail... tail) {
	string cur = "";
	for (auto ch: names){if(ch==','){break;}else{cur+=ch;}}
	string nxt = names.substr(cur.size()+2);
	cerr << cur << " = " << head << ", ";
	__f(nxt, tail...);
}

const int mxn = 200005;
int N, Q, S, T, ret;
int A[mxn], fw[mxn], fw2[mxn];

void update(int x, int y, int v) { 
    for (int tx=x; tx <= N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (int ty=y+1; ty <= N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
}
int sum(int x) {
    int res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res;
}
int query(int x, int y) { 
	if (x == 0) return A[0];
    return sum(y)-sum(x-1);
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> Q >> S >> T;
	for (int i = 0; i <= N; ++i) {
		cin >> A[i];
		if (i) update(i, i, A[i]);
	}
	for (int i = 0; i < N; ++i) {
		int dif = abs(A[i] - A[i + 1]);
		if (A[i] < A[i + 1]) ret -= dif * S;
		else ret += dif * T;
	}
	while (Q--) {
		int l, r, k;
		cin >> l >> r >> k;
		int lv = query(l - 1, l - 1), rv = query(r + 1, r + 1);
		int dif_l = query(l, l) - lv, dif_r = rv - query(r, r);
		if (dif_l > 0) ret += abs(dif_l) * S;
		else ret -= abs(dif_l) * T;
		if (r != N) {
			if (dif_r > 0) ret += abs(dif_r) * S;
			else ret -= abs(dif_r) * T;
		}

		update(l, r, k);
		dif_l = query(l, l) - lv, dif_r = rv - query(r, r);
		if (dif_l > 0) ret -= abs(dif_l) * S;
		else ret += abs(dif_l) * T;
		if (r != N) {
			if (dif_r > 0) ret -= abs(dif_r) * S;
			else ret += abs(dif_r) * T;
		}

		cout << ret << '\n';
	}
	return 0;
}

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