제출 #1179625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179625		patgra	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	190 ms	8344 KiB

foehn_phenomena

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;
    
ll tb;
vector<ll> t, ts;

ll tq(ll i) {
    i += tb;
    ll ret = 0;
    while(i) ret += t[i], i /= 2;
    return ret;
}
void ta(ll l, ll r, ll x) {
    l += tb;
    r += tb;
    t[l] += x;
    if(r != l) t[r] += x;
    while(l / 2 != r / 2) {
        if(l % 2 == 0) t[l + 1] += x;
        if(r % 2 == 1) t[r - 1] += x;
        l /= 2; r /= 2;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    ll n, q, s, T;
    cin >> n >> q >> s >> T;
    tb = 1 << (64 - __builtin_clzll(n));
    t.resize(tb * 2, 0);
    rep(i, 0, n + 1) cin >> t[tb + i];
    ll temp = 0;
    rep(i, 0, n) 
        temp += (t[tb + i] >= t[tb + i + 1] ? T * (t[tb + i] - t[tb + i + 1]) : -(s * (t[tb + i + 1] - t[tb + i])));
    rep(i, 0, q) {
        ll l, r, x;
        cin >> l >> r >> x;
        auto l1 = tq(l - 1), l2 = tq(l);
        if(l1 < l2) temp += s * (l2 - l1);
        if(l1 >= l2) temp -= T * (l1 - l2);
        if(r < n) {
            auto r1 = tq(r), r2 = tq(r + 1);
            if(r1 < r2) temp += s * (r2 - r1);
            if(r1 >= r2) temp -= T * (r1 - r2);
        }
        ta(l, r, x);
        l1 = tq(l - 1), l2 = tq(l);
        if(l1 < l2) temp -= s * (l2 - l1);
        if(l1 >= l2) temp += T * (l1 - l2);
        if(r < n) {
            auto r1 = tq(r), r2 = tq(r + 1);
            if(r1 < r2) temp -= s * (r2 - r1);
            if(r1 >= r2) temp += T * (r1 - r2);
        }
        cout << temp << '\n';
    }
}

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