Submission #477682

#	Time	Username	Problem	Language	Result	Execution time	Memory
477682		chungdinh	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	713 ms	13948 KiB

foehn_phenomena

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define ll long long
#define ii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define r first
#define c second

#define all(x) x.begin(), x.end()

ostream& operator << (ostream& os, pair<int, int> a) {
    return os << a.first << " : " << a.second;
}

#define endl '\n'
#define db(val) "["#val" = "<<(val)<<"] "
#define cntbit(x) __builtin_popcount(x)

const int N = 2e5 + 5;
const int iINF = 1e9;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1e18;

int n, q;
ll s, t;
int a[N];

ll A[N], S[N];
void upd(ll bit[N], int v, ll val) {
    for (; v <= n; v += v & -v) bit[v] += val;
}
ll get(ll bit[N], int v) {
    ll res = 0;
    for (;v >= 1; v -= v & -v) res += bit[v];
    return res;
}
ll point(ll bit[N], int v) {return get(bit, v) - get(bit, v - 1);}

int main() {
    #ifdef CHUNGDINH
    freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);
    #endif
    memset(A, 0ll, sizeof A);
    memset(S, 0ll, sizeof S);

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

    for (int i = 1; i <= n; i++) {
        upd(A, i, a[i] - a[i - 1]);

        ll tt;
        if (a[i] <= a[i - 1]) tt = t*(a[i - 1] - a[i]);
        else tt = -s*(a[i] - a[i - 1]);
        upd(S, i, tt);

       // cout << get(S, i) << " ";
    } //cout << endl;

    while (q--) {
        int l, r; ll x;
        cin >> l >> r >> x;

       // for (int i = 1; i <= n; i++) cout << get(S, i) - get(S, i - 1) << " "; cout << endl;

        //range update
        upd(A, l, x); upd(A, r + 1, -x);
        //for (int i = 1; i <= n; i++) cout << get(A, i) - get(A, i - 1) << " "; cout << endl;

        ll tt;
        ll tt1;

        { // l is always >= 1
            tt1 = point(A, l);

            //cout << tt1 << endl;

            if (tt1 > 0) tt = -s*(tt1);
            else tt = t*(-tt1);

            upd(S, l, -point(S, l) + tt);
        }

        if (r + 1 <= n) {
            tt1 = point(A, r + 1);

            if (tt1 > 0) tt = -s*(tt1);
            else tt = t*(-tt1);

            upd(S, r + 1, -point(S, r + 1) + tt);
        }

        //for (int i = 1; i <= n; i++) cout << get(S, i) - get(S, i - 1) << " "; cout << endl;
        cout << get(S, n) << endl;
    }
}

/*
Array bounds *
long long vs int
Garbage value
Sometimes, VNOI views "arrays out of bounds" as "wrong answer"
*/

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