Submission #717933

#	Time	Username	Problem	Language	Result	Execution time	Memory
717933		Markomafko972	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	154 ms	5628 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, q, k1, k2, a, z, l, r, d;
ll tren;
ll loga[200005];

void update(int x, int y) {
	x++;
	for (x; x <= n+1; x += x & -x) loga[x] += y;
}

ll query(int x) {
	ll out = 0;
	x++;
	for (x; x > 0; x -= x & -x) out += loga[x];
	return out;	
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> q >> k1 >> k2;
	for (int i = 0; i <= n; i++) {
		cin >> a;
		if (i > 0) {
			if (a > z) tren -= k1*(ll)(a-z);
			else tren += k2*(ll)(z-a);
		}
		z = a;
		update(i, a);
		update(i+1, -a);
	}
	
	for (int i = 0; i < q; i++) {
		cin >> l >> r >> d;
		ll br1 = query(l-1);
		ll br2 = query(l);
		if (br1 < br2) tren += k1*(ll)(br2-br1);
		else tren -= k2*(ll)(br1-br2);
		
		if (r+1 <= n) {
			ll br1 = query(r);
			ll br2 = query(r+1);
			if (br1 < br2) tren += k1*(ll)(br2-br1);
			else tren -= k2*(ll)(br1-br2);
		}
		
		update(l, d);
		update(r+1, -d);
		
		br1 = query(l-1);
		br2 = query(l);
		if (br1 < br2) tren -= k1*(ll)(br2-br1);
		else tren += k2*(ll)(br1-br2);
		
		if (r+1 <= n) {
			ll br1 = query(r);
			ll br2 = query(r+1);
			if (br1 < br2) tren -= k1*(ll)(br2-br1);
			else tren += k2*(ll)(br1-br2);
		}
		cout << tren << "\n";
	}

	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void update(int, int)':
foehn_phenomena.cpp:19:7: warning: statement has no effect [-Wunused-value]
   19 |  for (x; x <= n+1; x += x & -x) loga[x] += y;
      |       ^
foehn_phenomena.cpp: In function 'll query(int)':
foehn_phenomena.cpp:25:7: warning: statement has no effect [-Wunused-value]
   25 |  for (x; x > 0; x -= x & -x) out += loga[x];
      |       ^

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