Submission #777780

#	Time	Username	Problem	Language	Result	Execution time	Memory
777780		Sandarach151	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	145 ms	12368 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;

class segmentTree{
    private:
        int sze, upcost, downcost;
        vector<int> tree;
        vector<int> array;
        void privUpdate(int pos, int val, int curpos, int curleft, int curright){
            if(curleft==curright){
                array[curleft]+=val;
                if(array[curleft]>0){
                    tree[curpos]=array[curleft]*upcost;
                }
                else{
                    tree[curpos]=array[curleft]*downcost;
                }
            }
            else{
                int curmid = (curleft+curright)/2;
                if(pos<=curmid){
                    privUpdate(pos, val, 2*curpos+1, curleft, curmid);
                }
                else{
                    privUpdate(pos, val, 2*curpos+2, curmid+1, curright);
                }
                tree[curpos]=tree[2*curpos+1]+tree[2*curpos+2];
            }
        }
        int privGetSum(int qleft, int qright, int nodepos, int nodeleft, int noderight){
            if(qright<nodeleft || qleft>=noderight){
                return 0;
            }
            else if(qleft<=nodeleft && noderight<=qright){
                return tree[nodepos];
            }
            else{
                int nodemid = (nodeleft+noderight)/2;
                return privGetSum(qleft, qright, 2*nodepos+1, nodeleft, nodemid)+privGetSum(qleft, qright, 2*nodepos+2, nodemid+1, noderight);
            }
        }
    public:
        segmentTree(vector<int> vect, int _upcost, int _downcost): upcost(_upcost), downcost(_downcost), sze(vect.size()){
            array.resize(sze);
            tree.resize(4*sze, 0);
            privUpdate(0, 0, 0, 0, sze-1);
            for(int i=1; i<vect.size(); i++){
                privUpdate(i, vect[i]-vect[i-1], 0, 0, sze-1);
            }
        }
        int query(int left, int right, int val){
            privUpdate(left, val, 0, 0, sze-1);
            if(right!=sze-1){
                privUpdate(right+1, 0-val, 0, 0, sze-1);
            }
            return privGetSum(0, sze-1, 0, 0, sze-1);
        }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    vector<int> vect(n+1);
    for(int i=0; i<=n; i++){
        cin >> vect[i];
    }
    segmentTree tree(vect, 0-s, 0-t);
    for(int i=0; i<q; i++){
        int a, b, c;
        cin >> a >> b >> c;
        cout << tree.query(a, b, c) << '\n';
    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In constructor 'segmentTree::segmentTree(std::vector<int>, int, int)':
foehn_phenomena.cpp:6:26: warning: 'segmentTree::downcost' will be initialized after [-Wreorder]
    6 |         int sze, upcost, downcost;
      |                          ^~~~~~~~
foehn_phenomena.cpp:6:13: warning:   'int segmentTree::sze' [-Wreorder]
    6 |         int sze, upcost, downcost;
      |             ^~~
foehn_phenomena.cpp:43:9: warning:   when initialized here [-Wreorder]
   43 |         segmentTree(vector<int> vect, int _upcost, int _downcost): upcost(_upcost), downcost(_downcost), sze(vect.size()){
      |         ^~~~~~~~~~~
foehn_phenomena.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for(int i=1; i<vect.size(); i++){
      |                          ~^~~~~~~~~~~~

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