제출 #557924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557924		alextodoran	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	214 ms	12264 KiB

foehn_phenomena

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N, Q, S, T;
int A[N_MAX + 2];

ll Fen[N_MAX + 2];
void update (int pos, int val) {
    for (int i = pos; i <= N; i += i & -i) {
        Fen[i] += val;
    }
}
void update (int l, int r, int val) {
    update(l, val);
    update(r + 1, -val);
}
ll query (int pos) {
    ll val = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        val += Fen[i];
    }
    return val;
}

ll f (int i) {
    if (1 <= i && i <= N) {
        ll x = query(i - 1), y = query(i);
        return (x - y) * (x < y ? S : T);
    } else {
        return 0;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> Q >> S >> T;
    for (int i = 0; i <= N; i++) {
        cin >> A[i];
    }
    for (int i = 1; i <= N; i++) {
        update(i, i, A[i]);
    }
    ll answer = 0;
    for (int i = 1; i <= N; i++) {
        answer += f(i);
    }

    while (Q--) {
        int l, r, val;
        cin >> l >> r >> val;
        answer -= f(l) + f(r + 1);
        update(l, r, val);
        answer += f(l) + f(r + 1);
        cout << answer << "\n";
    }

    return 0;
}

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