Submission #629050

#	Time	Username	Problem	Language	Result	Execution time	Memory
629050		boris_mihov	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	420 ms	35756 KiB

foehn_phenomena

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;

llong n, q, s, t;
int a[MAXN];

struct Node
{
    llong left, right;
    llong sum, lazy;

    Node()
    {
        left = right = sum = lazy = 0;
    }

} tree[4*MAXN];

Node combine(Node left, Node right)
{
    Node res;
    res.left = left.left;
    res.right = right.right;
    res.sum = left.sum + right.sum;
    if (left.right <= right.left) res.sum -= s * (right.left - left.right);
    else res.sum += t * (left.right - right.left);
    return res;
}

void build(int l, int r, int node)
{
    if (l == r)
    {
        tree[node].left = a[l];
        tree[node].right = a[l];
        tree[node].lazy = 0;
        tree[node].sum = 0;
        return;
    }

    int mid = (l + r) / 2;
    build(l, mid, 2*node);
    build(mid + 1, r, 2*node + 1);
    tree[node] = combine(tree[2*node], tree[2*node + 1]);
}

void push(int node, int l, int r)
{
    if (tree[node].lazy == 0) return;

    tree[node].left += tree[node].lazy;
    tree[node].right += tree[node].lazy;
    if (l < r)
    {
        tree[2*node].lazy += tree[node].lazy;
        tree[2*node + 1].lazy += tree[node].lazy;
    }

    tree[node].lazy = 0;
}

void update(int l, int r, int node, int queryL, int queryR, int queryVal)
{
    push(node, l, r);
    if (queryR <  l || r <  queryL) return;
    if (queryL <= l && r <= queryR)
    {
        tree[node].lazy = queryVal;
        push(node, l, r);
        return;
    }

    int mid = (l + r) / 2;
    update(l, mid, 2*node, queryL, queryR, queryVal);
    update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
    tree[node] = combine(tree[2*node], tree[2*node + 1]);
}

void solve()
{
    int l, r, value;
    build(0, n, 1);
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> l >> r >> value;
        update(0, n, 1, l, r, value);
        std::cout << tree[1].sum << '\n';
    }
}

void read()
{
    std::cin >> n >> q >> s >> t;
    for (int i = 0 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

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