Submission #669703

#	Time	Username	Problem	Language	Result	Execution time	Memory
669703		soondro2266	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	603 ms	42956 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct seg{
    int l, r, val, s, t, mid;
    seg* ch[2] = {};
    seg(int _l, int _r, int _s, int _t, vector<int> &arr):l(_l),r(_r),s(_s),t(_t){
        if(l == r-1){
            val = arr[l];
            return;
        }
        mid = (l+r)/2;
        ch[0] = new seg(l, mid, s, t, arr);
        ch[1] = new seg(mid, r, s, t, arr);
        pull();
    }
    int get(){
        if(l == r-1){
            if(val < 0){
                return val*(0-t);
            }
            else{
                return val*(0-s);
            }
        }
        return val;
    }
    void pull(){
        val = ch[0]->get() + ch[1]->get();
    }
    void add(int idx, int k){
        if(l == r-1){
            val += k;
            return;
        }
        if(idx < mid){
            ch[0]->add(idx, k);
        }
        else{
            ch[1]->add(idx, k);
        }
        pull();
    }
    int query(int a, int b){
        if(a <= l && r <= b){
            return get();
        }
        int ans = 0;
        if(a < mid){
            ans += ch[0]->get();
        }
        if(b > mid){
            ans += ch[1]->get();
        }
        return ans;
    }
};
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    int sum;
    cin >> sum;
    vector<int> arr;
    for(int i = 0, tmp; i < n; i++){
        cin >> tmp;
        arr.push_back(tmp - sum);
        sum = tmp;
    }
    seg tr(0,n,s,t,arr);
    for(int i = 0, a, b, c; i < q; i++){
        cin >> a >> b >> c;
        a--;
        tr.add(a, c);
        if(b < n){
            tr.add(b, (0-c));
        }
        cout << tr.query(0, n) << endl;
    }
}

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