Submission #297465

#	Time	Username	Problem	Language	Result	Execution time	Memory
297465		Ahmad_Hasan	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	574 ms	28140 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

int n,m,ss,tt;
struct segmentTree{
    int sz=2;
    long long nl;
    vector<long long>s;
    vector<long long>t;
    vector<long long>operations,values;


    void updt(int i,long long vl){
        if(vl<=0){
            s[i]=vl*-1;
            t[i]=0;
        }else{
            s[i]=0;
            t[i]=vl;
        }
        for(i/=2;i>=1;i/=2){
            s[i]=s[i*2]+s[i*2+1];
            t[i]=t[i*2]+t[i*2+1];
        }
    }
    void build(vector<long long>v){
        for(int i=1;i<v.size();i++){
            updt(i+sz,v[i-1]-v[i]);
            values[i]=v[i];
        }
    }
    void init(int n,vector<long long>v){
        while(sz<n) sz*=2;
        operations=s=t=vector<long long>(2*sz,0);
        values=vector<long long>(2*sz,0);
        build(v);
        nl=n;
    }
    long long opera(long long x,long long y){
        if(y!=nl)
            return y;
        return x;
    }
    long long operation(long long &x,long long y){
        return x=opera(x,y);
    }


    void add(int l,int r,long long v,int x,int lx,int rx){
        if(rx<l||lx>r) return;
        if(lx>=l&&rx<=r){
            operations[x]+=v;
            if(rx+1>r&&rx+1<nl){
                ///cout<<get(rx)-get(rx+1)<<' '<<rx<<' '<<rx+1<<'\n';
                updt(rx+1+sz,get(rx)-get(rx+1));
            }

            if(lx-1<l){
                ///cout<<get(lx-1)-get(lx)<<' '<<lx-1<<' '<<lx<<'\n';
                updt(lx+sz,get(lx-1)-get(lx));
            }
            return;
        }
        int md=(lx+rx)/2;
        add(l,r,v,2*x,lx,md);
        add(l,r,v,2*x+1,md+1,rx);
    }

    void add(int l,int r,long long v){
        add(l,r,v,1,0,sz-1);
    }

    long long get(int i,int x,int lx,int rx){
        if(lx>=i&&(rx-lx+1)==1){
            return values[x-sz]+operations[x];
        }
        int md=(lx+rx)/2;
        long long res;
        if(i<=md){
            res=get(i,2*x,lx,md);
        }else{
            res=get(i,2*x+1,md+1,rx);
        }
        return res+operations[x];
    }
    long long get(int i){
        return get(i,1,0,sz-1);
    }
    long long answer(){
        return s[1]*ss*-1ll+t[1]*tt;
    }
     void print(){
        for(int i=1;i<=2*sz;i*=2){
            for(int j=i/2;j<i;j++){
                cout<<s[j]<<' ';
            }
            cout<<'\n';
        }
        for(int i=1;i<=2*sz;i*=2){
            for(int j=i/2;j<i;j++){
                cout<<t[j]<<' ';
            }
            cout<<'\n';
        }


     }
     void vals(){
        for(int i=0;i<nl;i++){
            cout<<get(i)<<' ';

        }
        cout<<'\n';
     }
};

int main()
{///{}
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    segmentTree st;
    cin>>n>>m>>ss>>tt;
    n++;
    vector<long long>v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    st.init(n,v);

    ///st.print();
    ///st.vals();
    while(m--){

            long long l,r,v;
            cin>>l>>r>>v;
            st.add(l,r,v);
            cout<<st.answer()<<'\n';
    }
    ///st.print();
    ///st.vals();
    return 0;
}
/**
3 5 1 2
0
40000000000
10000000000
80000000000
1 2 20000000000
1 1 -20000000000
2 3 50000000000
1 2 -10000000000
1 3 50000000000

*/

Compilation message (stderr)

foehn_phenomena.cpp: In member function 'void segmentTree::build(std::vector<long long int>)':
foehn_phenomena.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i=1;i<v.size();i++){
      |                     ~^~~~~~~~~

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