Submission #907593

#	Time	Username	Problem	Language	Result	Execution time	Memory
907593		andro	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	409 ms	24172 KiB

foehn_phenomena

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 5;

struct segtree{
    int t[4*N];
    int query(int v,int tl,int tr,int l,int r){
        if(tl>r||tr<l)return 0;
        if(tl >= l &&tr<=r)return t[v];
        int tm=(tl+tr)/2;
        return query(v*2,tl,tm,l,r)+query(v*2+1,tm+1,tr,l,r);
    }
    void update(int v,int tl,int tr,int index,int value){
        if(tl==tr)t[v]=value;
        else {
            int tm=(tl+tr)/2;
            if(index<=tm)update(v*2,tl,tm,index,value);
            else update(v*2+1,tm+1,tr,index,value);
            t[v]=t[v*2]+t[v*2+1];
        }
    }
    void update(int i, int v) {
        update(1, 0, N, i, v);
    }
    int query(int l, int r) {
        return query(1, 0, N, l, r);
    }
}seg1, seg2;

struct fenw {
    int t[N];
    int query(int i) {
        i += 1;
        int ans = 0;
        while(i) {
            ans += t[i];
            i -= i & - i;
        }
        return ans;
    }
    void update(int i, int v) {
        i += 1;
        while(i < N) {
            t[i] += v;
            i += i & - i;
        }
    }
}fenw;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    vector<int> a(n + 1);
    for(int i = 0; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        if(a[i] < a[i + 1]) {
            seg1.update(i, a[i + 1] - a[i]);
            seg2.update(i, 0);
        }
        else {
            seg2.update(i, a[i] - a[i + 1]);
            seg1.update(i, 0);
        }
    }
    for(int i = 0; i <= n; i++) {
        fenw.update(i, a[i]);
        fenw.update(i + 1, - a[i]);
    }
    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        fenw.update(l, x);
        fenw.update(r + 1, - x);
        /**
        for(int i = l; i <= r; i++) {
            a[i] += x;
        }
        int u1 = 0;
        int u2 = 0;
        for(int i = 0; i < n; i++) {
            if(a[i] < a[i + 1]) {
                //u -= s * (a[i + 1] - a[i]);
                u1 += a[i + 1] - a[i];
            }
            else {
                //u += t * (a[i] - a[i + 1]);
                u2 += a[i] - a[i + 1];
            }
        }
        cout << u2 * t << " " << u1 * s << "\n";**/
        if(l) {
            int idx = fenw.query(l - 1);
            int in = fenw.query(l);
            if(idx < in) {
                seg1.update(l - 1, in - idx);
                seg2.update(l - 1, 0);
            }
            else {
                seg1.update(l - 1, 0);
                seg2.update(l - 1, idx - in);
            }
        }
        if(l + 1 <= n) {
            int idx = fenw.query(l);
            int in = fenw.query(l + 1);
            if(idx < in) {
                seg1.update(l, in - idx);
                seg2.update(l, 0);
            }
            else {
                seg1.update(l, 0);
                seg2.update(l, idx - in);
            }
        }
        if(r) {
            int idx = fenw.query(r - 1);
            int in = fenw.query(r);
            if(idx < in) {
                seg1.update(r - 1, in - idx);
                seg2.update(r - 1, 0);
            }
            else {
                seg1.update(r - 1, 0);
                seg2.update(r - 1, idx - in);
            }
        }
        if(r + 1 <= n) {
            int idx = fenw.query(r);
            int in = fenw.query(r + 1);
            if(idx < in) {
                seg1.update(r, in - idx);
                seg2.update(r, 0);
            }
            else {
                seg1.update(r, 0);
                seg2.update(r, idx - in);
            }
        }
        cout << seg2.query(0, n - 1) * t - seg1.query(0, n - 1) * s << "\n";
    }
    //cout << fenw2.query(n) * t - fenw1.query(n) * s;
}

/*
mogu izvucem s i t pre zagrade
jedino sto se menja jeste razlika izmedju r i r + 1 i l i l - 1
*/

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