제출 #1340289

#제출 시각아이디문제언어결과실행 시간메모리
1340289nagorn_phFoehn Phenomena (JOI17_foehn_phenomena)C++20
0 / 100
17 ms7708 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};
const int N = 2e5 + 5;

int a[N], temp[N];

struct {
    int seg[4 * N], lazy[4 * N];
    void push(int l, int r, int i){
        seg[i] += lazy[i] * (r - l + 1);
        if (l != r) lazy[2 * i] += lazy[i], lazy[2 * i + 1] += lazy[i];
        lazy[i] = 0;
    }
    void build(int l, int r, int i){
        if (l == r) return seg[i] = temp[l], void();
        int mid = (l + r) / 2;
        build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
        seg[i] = seg[2 * i] + seg[2 * i + 1];
    }
    void update(int l, int r, int i, int ll, int rr, int val){
        push(l, r, i);
        if (l >= ll && r <= rr) return lazy[i] += val, push(l, r, i), void();
        if (r < ll || l > rr) return;
        int mid = (l + r) / 2;
        update(l, mid, 2 * i, ll, rr, val), update(mid + 1, r, 2 * i + 1, ll, rr, val);
        seg[i] = seg[2 * i] + seg[2 * i + 1];
    }
    int query(int l, int r, int i, int idx){
        push(l, r, i);
        if (l == r) return seg[i];
        int mid = (l + r) / 2;
        if (idx <= mid) return query(1, mid, 2 * i, idx);
        else return query(mid + 1, r, 2 * i + 1, idx);
    }
} seg;

void solve(){
    int n, q, s, t; cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) temp[i] = temp[i - 1] + (a[i - 1] < a[i] ? s * (a[i - 1] - a[i]) : t * (a[i - 1] - a[i]));
    seg.build(1, n, 1);
    while (q--) {
        int l, r, x; cin >> l >> r >> x;
        int dif = seg.query(1, n, 1, l) - (l == 1 ? 0ll : seg.query(1, n, 1, l - 1));
        int dh = 0;
        if (dif > 0) dh = -dif / t;
        else dh = -dif / s;
        dh += x;
        int newdif = (dh < 0 ? -dh * t : -dh * s);
        if (r < n) {
            int rdif = seg.query(1, n, 1, r + 1) - seg.query(1, n, 1, r);
            int rdh = 0;
            if (rdif > 0) rdh = -rdif / t;
            else rdh = -rdif / s;
            rdh -= x;
            int newrdif = (rdh < 0 ? -rdh * t : -rdh * s);
            seg.update(1, n, 1, r + 1, n, newrdif - rdif);
        }
        seg.update(1, n, 1, l, n, newdif - dif);
        cout << seg.query(1, n, 1, n) << "\n";
    }
}

int32_t main(){
    iShowSpeed;
    // int q; cin >> q; while (q--) 
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...