Submission #777782

#	Time	Username	Problem	Language	Result	Execution time	Memory
777782		Sandarach151	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	194 ms	19308 KiB

foehn_phenomena

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

class segmentTree{
    private:
        int sze;
        long long int upcost, downcost;
        vector<long long int> tree;
        vector<long long 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];
            }
        }
        long long 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<long long int> vect, long long int _upcost, long long 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);
            }
        }
        long long int query(int left, int right, long long 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;
    long long int s, t;
    cin >> n >> q >> s >> t;
    vector<long long 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;
        long long int 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<long long int>, long long int, long long int)':
foehn_phenomena.cpp:7:31: warning: 'segmentTree::downcost' will be initialized after [-Wreorder]
    7 |         long long int upcost, downcost;
      |                               ^~~~~~~~
foehn_phenomena.cpp:6:13: warning:   'int segmentTree::sze' [-Wreorder]
    6 |         int sze;
      |             ^~~
foehn_phenomena.cpp:44:9: warning:   when initialized here [-Wreorder]
   44 |         segmentTree(vector<long long int> vect, long long int _upcost, long long int _downcost): upcost(_upcost), downcost(_downcost), sze(vect.size()){
      |         ^~~~~~~~~~~
foehn_phenomena.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for(int i=1; i<vect.size(); i++){
      |                          ~^~~~~~~~~~~~

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