Submission #1115982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115982		mmdrzada	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	659 ms	14072 KiB

foehn_phenomena

#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef vector<ll> vi;
typedef vector<char> vc;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
 
#define sep ' '
#define F first
#define S second
#define fastIO   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define kill(x) {cout << x << endl;return;}
#define sz(x) ll(x.size())
#define SP(x) setprecision(x) 
#define mod(x) (1ll*x%M+M)%M
#define pq priority_queue
#define mid (l+r)/2
#define mid2 (l+r+1)/2
#define pll pair<ll, ll>
 
const ll INF = 1e9+1;
const ll N = 2e5+1;
const ll M = 1e9+7; // 998244353
int n, q, s, t;
ll w[N];
pair<ll, ll> node[N<<2]; // {value, lazy}
 
void dolazy(int id) {
	ll x = node[id].S;
	node[2*id].F += x;
	node[2*id].S += x;
	node[2*id+1].F += x;
	node[2*id+1].S += x;
	node[id].S = 0;
}
 
ll f(ll x, ll y) {
	return 1ll * (x-y) * (x < y ? s : t);
}
 
void build(int l=0, int r=n, int id=1) {
	if (r-l == 1) {
		node[id].F = w[l];
		return;
	}
	build(l, mid, 2*id), build(mid, r, 2*id+1);
}
 
void upd(int L, int R, ll x, int l=0, int r=n, int id=1) {
	if (R <= l || r <= L) return;
	if (L <= l && r <= R) {
		if (r-l == 1) node[id].F += x;
		node[id].S += x;
		return;
	}
	dolazy(id);
	upd(L, R, x, l, mid, 2*id), upd(L, R, x, mid, r, 2*id+1);
}
 
ll get(int i, int l=0, int r=n, int id=1) {
	if (r-l == 1) return node[id].F;
	dolazy(id);
	if (i < mid) return get(i, l, mid, 2*id);
	return get(i, mid, r, 2*id+1);
}
 
void solve() {
	cin >> n >> q >> s >> t;
	cin >> w[0];
	ll last = 0, tmp = 0;
	for(int i = 0 ; i < n ; i ++) cin >> w[i], tmp += f((i == 0 ? 0 : w[i-1]), w[i]);
	build();

	while(q--) {
		int l, r, ch; cin >> l >> r >> ch; l--;
		ll a, b, c, d;
		a = get(l), c = get(r-1);
		upd(l, r, ch);		
		b = get(l), d = get(r-1);
		
		ll x = (l == 0 ? 0 : get(l-1)), y = (r == n ? 0 : get(r));
		tmp += 0ll + f(x, b) - f(x, a) + (r == n ? 0 : 0ll + f(d, y) - f(c, y));
		cout << tmp << endl;	
	}
	
}
 
// check MAXN
int32_t main() {
	fastIO;
	
	solve();
	
	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void solve()':
foehn_phenomena.cpp:76:5: warning: unused variable 'last' [-Wunused-variable]
   76 |  ll last = 0, tmp = 0;
      |     ^~~~

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