Submission #115860

#	Time	Username	Problem	Language	Result	Execution time	Memory
115860		someone_aa	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	670 ms	20044 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
using namespace std;
const int maxn = 200100;
ll n, q, s, t;
ll a[maxn];

ll tree[4*maxn];
ll lazy[4*maxn];

void push_update(int li, int ri, int index) {
    if(lazy[index] != 0) {
        tree[index] += lazy[index];
        if(li != ri) {
            lazy[2*index] += lazy[index];
            lazy[2*index+1] += lazy[index];
        }
        lazy[index] = 0;
    }
}

void build(int li=0, int ri=n, int index=1) {
    if(li == ri) {
        tree[index] = a[li];
    }
    else {
        int mid = (li + ri) / 2;
        build(li, mid, 2*index);
        build(mid+1, ri, 2*index+1);
    }
}

void update(int ul, int ur, ll uval, int li=0, int ri=n, int index=1) {
    push_update(li, ri, index);
    if(li > ur || ri < ul) return;
    else if(li >= ul && ri <= ur) {
        lazy[index] += uval;
        push_update(li, ri, index);
    }
    else {
        int mid = (li + ri) / 2;
        update(ul,ur,uval,li,mid,2*index);
        update(ul,ur,uval,mid+1,ri,2*index+1);
        tree[index] = max(tree[2*index], tree[2*index+1]);
    }
}

ll query(int qind, int li=0, int ri=n, int index=1) {
    push_update(li, ri, index);
    if(li == ri) return tree[index];
    else {
        int mid = (li + ri) / 2;
        ll x;
        if(qind <= mid) x = query(qind, li, mid, 2*index);
        else x = query(qind, mid+1, ri, 2*index+1);

        tree[index] =  max(tree[2*index], tree[2*index+1]);
        return x;
    }
}

ll f(int i) {
    if(i == n) return 0LL;

    ll in = query(i+1);
    ll ic = query(i);

    ll diff = abs(in - ic);

    if(ic < in) return -diff * s;
    else return diff*t;
}

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

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

    build();
    ll result = 0LL;
    for(int i=0;i<=n;i++) {
        result += f(i);
    }

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

        result -= f(l-1);
        result -= f(r);
        update(l, r, v);

        result += f(l-1);
        result += f(r);

        cout<<result<<"\n";
    }

    return 0;
}

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