제출 #694135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
694135		DrearyJoke	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	434 ms	19748 KiB

foehn_phenomena

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define END "\n"
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T>
class LazySegTree {
    T MODIFY_ID, QUERY_ID; //Identity element - required argument
    public:
    int n;
    vector<T> st, op;
    LazySegTree () {
        ;
    }
    LazySegTree (int sz, const T _QUERY_ID, const T _MODIFY_ID, const vector<T>& A = {}) 
    : QUERY_ID(_QUERY_ID), MODIFY_ID(_MODIFY_ID) {
        //Initialising 
        n = 1;
        while (n < sz) n <<= 1;
        st.resize(n << 1, QUERY_ID);
        op.resize(n << 1, MODIFY_ID);
        if (A.size()) {
            build(A, 0, 0, n);
        }
    }
    
    inline T binary_query(const T& a, const T& b) const {
        return a + b;
    }

    inline void binary_modify(T& a, const T& b) {
        a += b;
    }

    void propagate(int x, int lx, int rx) {
        if (rx - lx == 1 || op[x] == MODIFY_ID) return;
        int a = (x << 1) | 1, b = (x << 1) + 2;
        binary_modify(st[a], op[x]);
        binary_modify(op[a], op[x]);
        binary_modify(st[b], op[x]);
        binary_modify(op[b], op[x]);
        op[x] = MODIFY_ID;
    }
    
    void build(const vector<T>& A, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < (int)A.size()) {
                st[x] = A[lx];
            }
            return;
        }
        int mid = (lx + rx) >> 1, a = (x << 1) | 1, b = (x << 1) + 2;
        build(A, a, lx, mid);
        build(A, b, mid, rx);
        st[x] = binary_query(st[a], st[b]);
    }
    void update(int l, int r, const T& val, int x, int lx, int rx) {
        if (lx >= r  || rx <= l) return;
        if (lx >= l && rx <= r) {
            binary_modify(st[x], val);
            binary_modify(op[x], val);
            return;
        }
        propagate(x, lx, rx);
        int mid = (lx + rx) >> 1, a = (x << 1) | 1, b = (x << 1) + 2;
        update(l, r, val, a, lx, mid);
        update(l, r, val, b, mid, rx);
        st[x] = binary_query(st[a], st[b]);
    }
    void update(int l, int r, const T& val) {
        update(l, r, val, 0, 0, n);
    }

    T query(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return QUERY_ID;
        if (lx >= l && rx <= r) return st[x];
        propagate(x, lx, rx);
        int mid = (lx + rx) >> 1, a = (x << 1) | 1, b = (x << 1) + 2;
        return binary_query(query(l, r, a, lx, mid), query(l, r, b, mid, rx));
    }
    T query(int l, int r) {
        return query(l, r, 0, 0, n);
    }
};

void solve(){
    ll n, q, s, t;
    cin >> n >> q >> s >> t;
    vector<ll> A(n + 1);
    for (int i = 0; i <= n; ++i) cin >> A[i];
    LazySegTree<ll> st(n + 1, 0, 0, A);
    ll temp = 0;
    auto get_change = [&] (ll a, ll b) {
        if (b > a) return -s * (b - a);
        else return t * (a - b); 
    };
    for (int i = 1; i <= n; ++i) {
        temp += get_change(A[i - 1], A[i]);
    }
    auto update = [&] (int x, ll v, int T) {
        if (T == 0) {
            if (x == 0) return;
            ll a = st.query(x - 1, x), b = st.query(x, x + 1);
            temp -= get_change(a, b);
            temp += get_change(a, b + v);
        } else {
            if (x == n) return;
            ll a = st.query(x, x + 1), b = st.query(x + 1, x + 2);
            temp -= get_change(a, b);
            temp += get_change(a + v, b);
        }
    };
    while (q--) {
        ll l, r, v;
        cin >> l >> r >> v;
        update(l, v, 0);
        update(r, v, 1);
        st.update(l, r + 1, v);
        cout << temp << '\n';
    }
}
int main()
{
    fastio
    int t = 1;
    // cin>> t;
    while(t--) solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

foehn_phenomena.cpp: In instantiation of 'LazySegTree<T>::LazySegTree(int, T, T, const std::vector<_Tp>&) [with T = long long int]':
foehn_phenomena.cpp:109:38:   required from here
foehn_phenomena.cpp:26:18: warning: 'LazySegTree<long long int>::QUERY_ID' will be initialized after [-Wreorder]
   26 |     T MODIFY_ID, QUERY_ID; //Identity element - required argument
      |                  ^~~~~~~~
foehn_phenomena.cpp:26:7: warning:   'long long int LazySegTree<long long int>::MODIFY_ID' [-Wreorder]
   26 |     T MODIFY_ID, QUERY_ID; //Identity element - required argument
      |       ^~~~~~~~~
foehn_phenomena.cpp:33:5: warning:   when initialized here [-Wreorder]
   33 |     LazySegTree (int sz, const T _QUERY_ID, const T _MODIFY_ID, const vector<T>& A = {})
      |     ^~~~~~~~~~~

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