제출 #1310358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310358		LeonaRaging	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	92 ms	7408 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define db(val) "[" #val " = " << (val) << "] "

const int maxn = 2e5 + 4;
const int mod = 1e9 + 7;

int n, q, s, t, a[maxn], bit[maxn];

void updatePoint(int u, int v) {
    int idx = u;
    while (idx <= n) {
        bit[idx] += v;
        idx += (idx & (-idx));
    }
}

void updateRange(int l, int r, int v) {
    updatePoint(l, v);
    updatePoint(r + 1, -v);
}

int get(int u) {
    if (u == 0) return a[0];
    if (u == n + 1) u = n;
    int idx = u, ans = 0;
    while (idx > 0) {
        ans += bit[idx];
        idx -= (idx & (-idx));
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("inputf.in", "r", stdin);
    cin >> n >> q >> s >> t;
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        cin >> a[i]; 
        if (i > 0) {
            updateRange(i, i, a[i]);
            int dif = a[i] - a[i - 1];
            sum -= dif * (dif > 0 ? s : t);
        }
    }
    while (q--) {
        int l, r, k; cin >> l >> r >> k;
        int dif;

        dif = get(l) - get(l - 1);
        sum += dif * (dif > 0 ? s : t);
        dif = get(r + 1) - get(r);
        // clog << db(r) << db(r + 1) << dif << '\n';
        sum += dif * (dif > 0 ? s : t);

        updateRange(l, r, k);

        dif = get(l) - get(l - 1);
        sum -= dif * (dif > 0 ? s : t);
        dif = get(r + 1) - get(r);
        sum -= dif * (dif > 0 ? s : t);
        cout << sum << '\n';
    }
}

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