Submission #536158

#	Time	Username	Problem	Language	Result	Execution time	Memory
536158		Tadiorn	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	606 ms	16936 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define INF 1000000000
#define LINF 1000000000000000000
#define pb push_back
using namespace std;
#define MAXN 200010

ll a[MAXN];
ll seg[4*MAXN];
ll lazy[4*MAXN];

void propagate(int node, int l, int r){
    if(l == r){
        seg[node] += lazy[node];
        lazy[node] = 0;
        return;
    }
    lazy[2*node] += lazy[node]; lazy[2*node+1] += lazy[node];
    lazy[node] = 0;
    return;
}
void update(int node, int l, int r, int L, int R, ll x){
    //cout << "START " << node << ", " << l << ", " << r << endl;
    propagate(node, l, r);
    if(L <= l && r <= R){
        lazy[node] += x;
        propagate(node, l, r);
        //cout << "END2 " << node << ", " << l << ", " << r << endl;
        return;
    }
    int mid = (l+r)/2;
    if(L <= mid) update(2*node, l, mid, L, R, x);
    if(R > mid) update(2*node+1, mid+1, r, L, R, x);
    //cout << "END " << node << ", " << l << ", " << r << endl;
 //   propagate(2*node, l, mid);
 //   propagate(2*node+1, mid+1, r);
}
ll query(int node, int l, int r, int idx){
    propagate(node, l, r);
    if(l == r) return seg[node];
    int mid = (l+r)/2;
    if(idx <= mid) return query(2*node, l, mid, idx);
    else return query(2*node+1, mid+1, r, idx);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q; ll s, t;
    cin >> n >> q >> s >> t; s = -s;
    for(int i = 1; i <= n+1; i++){
        cin >> a[i];
        update(1, 1, n+1, i, i, a[i]);
    }
    /*cout << seg[1] << endl;
    cout << seg[2] << " " << seg[3] << endl;
    cout << seg[4] << " " << seg[5] << " " << seg[6] << " " << seg[7] << endl;*/
    ll res = 0;
    for(int i = 2; i <= n+1; i++){
        if(a[i] > a[i-1]) res += s * (a[i]-a[i-1]);
        else res += t * (a[i-1]-a[i]);
    }
   /// cout << "res: " << res << endl;
    while(q--){
        int l, r, x; cin >> l >> r >> x; l++, r++;
       /** cout << query(1, 1, n+1, 1) << ", ";
        cout << query(1, 1, n+1, 2) << ", ";
        cout << query(1, 1, n+1, 3) << ", ";
        cout << query(1, 1, n+1, 4) << endl;*/
        int d = query(1, 1, n+1, l) - query(1, 1, n+1, l-1);
        ///cout << "dl: " << d << ", dl2: " << d+x << endl;
        /*if(d > 0 && d+x <= 0) res += d*s+(x-d)*t;
        else if(d <= 0 && d+x > 0) res -= (-d)*t+(d+x)*s;
        else if(d > 0 && d+x > 0) res -= x*s;
        else res += -x*t;*/
        if(d > 0 && d+x <= 0){res -= d*s; res += -(d+x)*t;}
        else if(d <= 0 && d+x > 0){res -= t*(-d); res += (d+x)*s;}
        else if(d > 0 && d+x > 0){res -= s*d; res += s*(d+x);}
        else{res -= t*(-d); res += (-d+x)*t;}

        if(r < n+1){
            d = query(1, 1, n+1, r+1) - query(1, 1, n+1, r);
            ///cout << "dr: " << d << ", dr2: " << d-x << endl;
            /*if(d > 0 && d-x <= 0) res += d*s+(x-d)*t;
            else if(d <= 0 && d-x > 0) res -= (-d)*t+(d-x)*s;
            else if(d > 0 && d-x > 0) res -= -x*s;
            else res += x*s;*/
            if(d > 0 && d-x <= 0){res -= d*s; res += -(d-x)*t;}
            else if(d <= 0 && d-x > 0){res -= (-d)*t; res += (d-x)*s;}
            else if(d > 0 && d-x > 0){res -= d*s; res += (d-x)*s;}
            else{res -= (-d)*t; res += -(d-x)*t;}
        }
        update(1, 1, n+1, l, r, x);
        cout << res << endl;
    }
    return 0;
}

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