제출 #1175705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175705		Roumak77	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	523 ms	13572 KiB

foehn_phenomena

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

using ll = long long;

ll create(ll node, ll l, ll r, vector<ll>& tree, vector<ll>& main_arr)
{
    if (l == r)
    {
        tree[node] = main_arr[l];
        return tree[node];
    }


    ll mid = (l + r) / 2;
    ll left_child = create(2 * node, l, mid, tree, main_arr);
    ll right_child = create(2 * node + 1, mid + 1, r, tree, main_arr);

    tree[node] = left_child + right_child;
    return tree[node];
}

ll query(ll node, ll l, ll r, vector<ll>& tree, ll l_req, ll r_req)
{
    if (r < l_req || r_req < l)
    {
        return 0;
    }

    if (l_req <= l && r <= r_req)
    {
        return tree[node];
    }

    ll mid = (l + r) / 2;
    ll left_child = query(2 * node, l, mid, tree, l_req, r_req);
    ll right_child = query(2 * node + 1, mid + 1, r, tree, l_req, r_req);

    return left_child + right_child;
}


ll upd(ll node, ll l, ll r, vector<ll>& tree, ll idx, ll delta)
{
    if (l > idx || r < idx)
    {
        return tree[node];
    }

    if (l == r && l == idx && r == idx)
    {
        tree[node] += delta;
        return tree[node];
    }

    ll mid = (l + r) / 2;
    ll left_child = upd(2 * node, l, mid, tree, idx, delta);
    ll right_child = upd(2 * node + 1, mid + 1, r, tree, idx, delta);
    tree[node] = left_child + right_child;
    return tree[node];
}

void solve()
{
    ll n, q, s, t;
    cin >> n >> q >> s >> t;

    vector<ll> v(n + 1, 0);
    for (ll i = 0; i <= n; i++)
    {
        cin >> v[i];
    }

    ll pos = 0;
    ll neg = 0;

    for (ll i = 1; i <= n; i++)
    {
        if (v[i] <= v[i - 1])
        {
            pos += v[i - 1] - v[i];
        }
        else
        {
            neg += v[i] - v[i - 1];
        }
    }


    vector<ll> temp(n + 2, 0);
    vector<ll> tree(4 * n + 8, 0);
    create(1, 0, n + 1, tree, temp);


    for (ll i = 0; i < q; i++)
    {
        ll l, r, k;
        cin >> l >> r >> k;

        //cout << pos << " " << neg << endl;


        // first do left_shenanigans
        ll prev = v[l - 1] + query(1, 0, n + 1, tree, 0, l - 1);
        ll curr = v[l] + query(1, 0, n + 1, tree, 0, l);
        ll next = v[l + 1] + query(1, 0, n + 1, tree, 0, l + 1);

        if (next <= curr)
        {
            pos -= curr - next;
        }
        else
        {
            neg -= next - curr;
        }


        if (prev >= curr)
        {
            pos -= prev - curr;
        }
        else
        {
            neg -= curr - prev;
        }


        //cout << prev << " " << curr << " " << next << endl;
        //cout << pos << " " << neg << endl;


        if (l != r)
        {
            // right_shenanigans
            prev = v[r - 1] + query(1, 0, n + 1, tree, 0, r - 1);
            curr = v[r] + query(1, 0, n + 1, tree, 0, r);
            next = v[r + 1] + query(1, 0, n + 1, tree, 0, r + 1);

            //cout << "r + 1 = " << r + 1 << endl;
            if (r != n)
            {
                if (next <= curr)
                {
                    pos -= curr - next;
                }
                else
                {
                    neg -= next - curr;
                }
            }


            if (r != l + 1)
            {
                if (prev >= curr)
                {
                    pos -= prev - curr;
                }
                else
                {
                    neg -= curr - prev;
                }
            }
            //cout << prev << " " << curr << " " << next << endl;
            //cout << pos << " " << neg << endl;
        }


        // update left
        upd(1, 0, n + 1, tree, l, k);
        if (r != n)
        {
            upd(1, 0, n + 1, tree, r + 1, -k);

        }

        prev = v[l - 1] + query(1, 0, n + 1, tree, 0, l - 1);
        curr = v[l] + query(1, 0, n + 1, tree, 0, l);
        next = v[l + 1] + query(1, 0, n + 1, tree, 0, l + 1);

        if (next <= curr)
        {
            pos += curr - next;
        }
        else
        {
            neg += next - curr;
        }

        if (prev >= curr)
        {
            pos += prev - curr;
        }
        else
        {
            neg += curr - prev;
        }

        //cout << prev << " " << curr << " " << next << endl;
        //cout << pos << " " << neg << endl;


        //upd(1, 0, n + 1, tree, r + 1, -k);
        if (l != r)
        {
            prev = v[r - 1] + query(1, 0, n + 1, tree, 0, r - 1);
            curr = v[r] + query(1, 0, n + 1, tree, 0, r);
            next = v[r + 1] + query(1, 0, n + 1, tree, 0, r + 1);

            if (r != n)
            {
                if (next <= curr)
                {
                    pos += curr - next;
                }
                else
                {
                    neg += next - curr;
                }
            }



            if (r != l + 1)
            {
                if (prev >= curr)
                {
                    pos += prev - curr;
                }
                else
                {
                    neg += curr - prev;
                }
            }
        }


        //cout << prev << " " << curr << " " << next << endl;

        //cout << pos << " " << neg << endl;


        cout << pos * t - neg * s << endl;
    }
}

bool single = true;

signed main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;
    if (!single) cin >> t;

    while (t--)
    {
        solve();
    }
}

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