Submission #670451

#	Time	Username	Problem	Language	Result	Execution time	Memory
670451		fatemetmhr	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	149 ms	7264 KiB

foehn_phenomena

// ~ Be Name Khoda ~

#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

ll s, t, all = 0, fen[maxn5], a[maxn5];


inline void add(int id, ll val){
    all += val;
    for(id++; id < maxn5; id += id & -id)
        fen[id] += val;
}

inline ll get(int id){
    ll ret = all + a[id];
    if(!id)
        return ret;
    for(; id; id -= id & -id)
        ret -= fen[id];
    return ret;
}

inline ll get_val(ll a, ll b){
    return abs(a - b) * (a < b ? -s : t);
}

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

    int n, q;
    cin >> n >> q >> s >> t;
    ll cur = 0;
    for(int i = 0; i <= n; i++){
        cin >> a[i];
        if(i)
            cur += get_val(a[i - 1], a[i]);
    }
    while(q--){
        int l, r, x; cin >> l >> r >> x;
        //cout << "ok " << l << ' ' << r << endl;
        if(l)
            cur -= get_val(get(l - 1), get(l));
        if(r < n)
            cur -= get_val(get(r), get(r + 1));
        add(r, x);
        if(l)
            add(l - 1, -x);
        if(l)
            cur += get_val(get(l - 1), get(l));
        if(r < n)
            cur += get_val(get(r), get(r + 1));
        cout << cur << '\n';
    }
}

/*
Why so fast...? 
Hold on...
Hold your breath...
Need anything else?

Nein, Kein Problem...
Das Leben war schon immer so grausam :)
*/

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