Submission #1017260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017260		vjudge1	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	168 ms	262144 KiB

foehn_phenomena

#include<iostream>
#include<vector>
using namespace std;
struct SegmentTree {
    struct Node {
        int height;
        int pending_change;
    };
    vector<Node> tree;
    int n;
    SegmentTree(int size) {
        n=size;
        tree.resize(4*n);
        build(0,0,n-1);
    }
    void build(int v,int tl,int tr) {
        if(tl==tr) {
            tree[v]={0,0}; 
        } else {
            int tm=(tl+tr)/2;
            build(v*2+1, tl,tm);
            build(v*2+2, tm+1,tr);
            tree[v]={0,0};
        }
    }
    void update(int v,int tl,int tr,int l,int r,int change) {
        if(l>r) return;
        if(tl==l&&tr==r) {
            tree[v].pending_change+=change;
        } else {
            int tm=(tl+tr)/2;
            update(v*2+1,tl,tm,l,min(r,tm),change);
            update(v*2+2,tm+1,tr,max(l,tm+1),r,change);
        }
    }
    int get_temperature(int v,int tl,int tr,int position,int temperature) {
        if(tl==tr) {
            return temperature+tree[v].pending_change;
        } else {
            int tm=(tl+tr)/2;
            if(position<=tm) {
                return get_temperature(v*2+1,tl,tm,position,temperature+tree[v].pending_change);
            } else {
                return get_temperature(v*2+2,tm+1,tr,position,temperature+tree[v].pending_change);
            }
        }
    }
    void process_movement(int L,int R,int X) {
        update(0,0,n-1,L,R,X);
    }
};
int main() {
    int N,Q,S,T;
    cin>>N>>Q>>S>>T;
    vector<int> A(N+1);
    for(int i=1; i<=N; ++i) {
        cin>>A[i];
    }
    SegmentTree st(N+1);
    for(int day=0; day<Q; ++day) {
        int L,R,X;
        cin>>L>>R>>X;
        st.process_movement(L,R,X);
        int wind_temperature=0;
        for(int i=1; i<=N; ++i) {
            int height_current=st.get_temperature(0,0,N-1,i,0);
            int height_previous=st.get_temperature(0,0,N-1,i-1,0);
            if(height_current>height_previous) {
                wind_temperature-=S*(height_current-height_previous);
            } else if(height_current<height_previous) {
                wind_temperature+=T*(height_previous-height_current);
            }
        }
        cout<<wind_temperature<<endl;
    }
    return 0;
}

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