제출 #1293741

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293741		muhammad-ahmad	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	492 ms	22092 KiB

foehn_phenomena

// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
using namespace std;

#define int long long
#define endl "\n"

const int N = 2e5 + 5;
int n;

struct node{
	int s = 0, mi = 0, mx = 0, lazy = 0;
} T[4 * N];

node pull(node lc, node rc){
	node res;
	res.mi = min(lc.mi, rc.mi);
	res.mx = max(lc.mx, rc.mx);
	res.s = lc.s + rc.s;
	return res;
}

void push(int s, int e, int v){
	int mid = (e + s) / 2, lc = 2 * v, rc = lc + 1;
	
	T[lc].mi += T[v].lazy;
	T[lc].mx += T[v].lazy;
	T[lc].s += T[v].lazy * (mid - s);
	T[lc].lazy += T[v].lazy;
	
	T[rc].mi += T[v].lazy;
	T[rc].mx += T[v].lazy;
	T[rc].s += T[v].lazy * (e - mid);
	T[rc].lazy += T[v].lazy;
	
	T[v].lazy = 0;
}

void update(int val, int l, int r, int s = 0, int e = n, int v = 1){
	if (l >= e or s >= r) return;
	if (l <= s and e <= r){
		T[v].mi += val;
		T[v].mx += val;
		T[v].s += val * (e - s);
		T[v].lazy += val;
		return;
	}
	
	int mid = (e + s) / 2, lc = 2 * v, rc = lc + 1;
	push(s, e, v);
	
	update(val, l, r, s, mid, lc);
	update(val, l, r, mid, e, rc);
	T[v] = pull(T[lc], T[rc]);
}

node get(int l, int r, int s = 0, int e = n, int v = 1){
	if (l <= s && e <= r){
		return T[v];
	}
	
	int mid = (e + s) / 2, lc = 2 * v, rc = lc + 1;
	push(s, e, v);
	
	if (l < mid){
		node res = get(l, r, s, mid, lc);
		if (r > mid){
			res = pull(res, get(l, r, mid, e, rc));
		}
		return res;
	}
	return get(l, r, mid, e, rc);
}

void solve() {
	int q, s, t; cin >> n >> q >> s >> t;
	n++;
	int A[n];
	int ans = 0;
	for (int i = 0; i < n; i++){
		int x; cin >> x;
		A[i] = x;
		update(x, i, i + 1);
		if (i > 0 && A[i] > A[i - 1]) ans -= (A[i] - A[i - 1]) * s;
		else if (i > 0) ans += (A[i - 1] - A[i]) * t;
	}
	
	for (int Q = 1;  Q <= q; Q++){
		int l, r, x; cin >> l >> r >> x;
		int vl1 = get(l - 1, l).s, vl2 = get(l, l + 1).s;
		if (vl1 < vl2) ans += (vl2 - vl1) * s;
		else ans -= (vl1 - vl2) * t;
		if (r < n - 1){
			int vr1 = get(r, r + 1).s, vr2 = get(r + 1, r + 2).s;
			if (vr1 < vr2) ans += (vr2 - vr1) * s;
			else ans -= (vr1 - vr2) * t;
		}
		update(x, l, r + 1);
		vl1 = get(l - 1, l).s, vl2 = get(l, l + 1).s;
		if (vl1 < vl2) ans -= (vl2 - vl1) * s;
		else ans += (vl1 - vl2) * t;
		if (r < n - 1){
			int vr1 = get(r, r + 1).s, vr2 = get(r + 1, r + 2).s;
			if (vr1 < vr2) ans -= (vr2 - vr1) * s;
			else ans += (vr1 - vr2) * t;
		}
		cout << ans << endl;
	}
	
    return;
}

signed main() {
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);	
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << setprecision(9);
    srand(time(0));

    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

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