oj.uz

Submission #694135

# Submission time Handle Problem Language Result Execution time Memory
694135 2023-02-03T22:39:36 Z DrearyJoke Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 434 ms 19748 KB 
#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;
}

Compilation message

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 388 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 5 ms 456 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 16912 KB Output is correct
2 Correct 381 ms 17716 KB Output is correct
3 Correct 389 ms 18064 KB Output is correct
4 Correct 413 ms 17476 KB Output is correct
5 Correct 385 ms 18776 KB Output is correct
6 Correct 224 ms 17696 KB Output is correct
7 Correct 199 ms 17708 KB Output is correct
8 Correct 381 ms 18404 KB Output is correct
9 Correct 383 ms 18820 KB Output is correct
10 Correct 326 ms 17536 KB Output is correct
11 Correct 230 ms 17540 KB Output is correct
12 Correct 201 ms 18364 KB Output is correct
13 Correct 204 ms 18540 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 388 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 5 ms 456 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 376 ms 16912 KB Output is correct
23 Correct 381 ms 17716 KB Output is correct
24 Correct 389 ms 18064 KB Output is correct
25 Correct 413 ms 17476 KB Output is correct
26 Correct 385 ms 18776 KB Output is correct
27 Correct 224 ms 17696 KB Output is correct
28 Correct 199 ms 17708 KB Output is correct
29 Correct 381 ms 18404 KB Output is correct
30 Correct 383 ms 18820 KB Output is correct
31 Correct 326 ms 17536 KB Output is correct
32 Correct 230 ms 17540 KB Output is correct
33 Correct 201 ms 18364 KB Output is correct
34 Correct 204 ms 18540 KB Output is correct
35 Correct 389 ms 17060 KB Output is correct
36 Correct 392 ms 18456 KB Output is correct
37 Correct 404 ms 19240 KB Output is correct
38 Correct 364 ms 19060 KB Output is correct
39 Correct 386 ms 19072 KB Output is correct
40 Correct 383 ms 19004 KB Output is correct
41 Correct 404 ms 18884 KB Output is correct
42 Correct 412 ms 19132 KB Output is correct
43 Correct 434 ms 18260 KB Output is correct
44 Correct 367 ms 18648 KB Output is correct
45 Correct 400 ms 18800 KB Output is correct
46 Correct 386 ms 19748 KB Output is correct
47 Correct 195 ms 18328 KB Output is correct
48 Correct 204 ms 18240 KB Output is correct
49 Correct 364 ms 17420 KB Output is correct
50 Correct 227 ms 18124 KB Output is correct
51 Correct 209 ms 18504 KB Output is correct
52 Correct 227 ms 18296 KB Output is correct