Submission #587142

#	Time	Username	Problem	Language	Result	Execution time	Memory
587142		TheEvilBird	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	454 ms	38244 KiB

foehn_phenomena

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

#ifdef __APPLE__
#include "debug.h"
//#define debug(...) 42
#else
#define debug(...) 42
#endif

ll s, t;

struct SegTree {
    struct Node {
        ll T, l, r, pushed;
    };

    int n, qL, qR, index;
    ll val, ans;
    const ll off = 0;

    vector<Node> tree;
    vector<ll> a;

    SegTree(int _n) {
        n = _n;
        tree.assign(4 * n, {0, 0, 0, off});
    }

    void update_vertex(int v, int l, int r) {
        int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
        push(vL, l, m);
        push(vR, m, r);
        tree[v].T = tree[vL].T + tree[vR].T;
        if (tree[vL].r < tree[vR].l) {
            tree[v].T -= s * (tree[vR].l - tree[vL].r);
        }
        else if (tree[vL].r > tree[vR].l) {
            tree[v].T += t * (tree[vL].r - tree[vR].l);
        }
        tree[v].l = tree[vL].l;
        tree[v].r = tree[vR].r;
    }

    void push(int v, int l, int r) {
        if (tree[v].pushed == off) return;
        int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
        tree[v].l += tree[v].pushed;
        tree[v].r += tree[v].pushed;
        if (l + 1 != r) {
            tree[vL].pushed += tree[v].pushed;
            tree[vR].pushed += tree[v].pushed;
        }
        tree[v].pushed = off;
    }

    void build(vector<ll> &_a) {
        a = _a;
        build_tree(1, 0, n);
    }

    void build_tree(int v, int l, int r) {
        if (l + 1 == r) {
            tree[v] = {0, a[l], a[l], off};
            return;
        }
        int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
        build_tree(vL, l, m);
        build_tree(vR, m, r);
        update_vertex(v, l, r);
    }

    void update_segment(int _qL, int _qR, ll _val) {
        qL = _qL;
        qR = _qR + 1;
        val = _val;
        update_segment_tree(1, 0, n);
    }

    void update_segment_tree(int v, int l, int r) {
        push(v, l, r);
        if (qL <= l && r <= qR) {
            tree[v].pushed += val;
            push(v, l, r);
            return;
        }
        int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
        if (qL < m) update_segment_tree(vL, l, m);
        if (m < qR) update_segment_tree(vR, m, r);
        update_vertex(v, l, r);
    }

    ll get_all() {
        return tree[1].T;
    }
};

void solve() {
    int n, q;
    cin >> n >> q >> s >> t;
    vector<ll> a(n + 1);
    for (auto &i: a) cin >> i;
    SegTree tr(n + 1);
    tr.build(a);
    while (q--) {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        tr.update_segment(l, r, x);
        cout << tr.get_all() << en;
    }
}

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In member function 'void SegTree::push(int, int, int)':
foehn_phenomena.cpp:84:13: warning: unused variable 'm' [-Wunused-variable]
   84 |         int m = (l + r) / 2, vL = 2 * v, vR = vL + 1;
      |             ^

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