제출 #1116144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116144		staszic_ojuz	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	111 ms	13752 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

using ll=long long;

const int MAX=2*1e5+7;
const int base=1<<20;

ll drzewo[2*base];

void ppush(int a, int b, ll w){
    a += base-1;
    b += base+1;
    while (a/2!=b/2){
        if (a%2==0) drzewo[a+1]+=w;
        if (b%2==1) drzewo[b-1]+=w;
        a/=2;
        b/=2;
    }
}

void get(int a){
    int a2=a;
    a+=base;
    ll wyn=0;
    while (a>0){
        wyn += drzewo[a];
        a /= 2;
    }
    drzewo[base+a2] = wyn;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, q, l, r;
    ll s, t, x, wyn=0;
    cin >> n >> q >> s >> t;

    cin >> drzewo[base];
    for (int i=1; i<=n; i++){
        cin >> drzewo[base+i];
        if (drzewo[base+i-1] < drzewo[base+i]) wyn -= s*(drzewo[base+i]-drzewo[base+i-1]);
        else wyn += t*(drzewo[base+i-1]-drzewo[base+i]);
    }

    for (int i=0; i<q; i++){
        cin >> l >> r >> x;
        //cout << wyn << endl;
        if (drzewo[base+l-1] < drzewo[base+l]) wyn += s*(drzewo[base+l]-drzewo[base+l-1]);
        else wyn -= t*(drzewo[base+l-1]-drzewo[base+l]);

        if (r!=n){
            if (drzewo[base+r] < drzewo[base+r+1]) wyn += s*(drzewo[base+r+1]-drzewo[base+r]);
            else wyn -= t*(drzewo[base+r+1]-drzewo[base+r]);
        }
        //cout << wyn << endl;
        ppush(l, r, x);
        get(l);
        get(r);
        if (drzewo[base+l-1] < drzewo[base+l]) wyn -= s*(drzewo[base+l]-drzewo[base+l-1]);
        else wyn += t*(drzewo[base+l-1]-drzewo[base+l]);

        if (r!=n){
            if (drzewo[base+r] < drzewo[base+r+1]) wyn -= s*(drzewo[base+r+1]-drzewo[base+r]);
            else wyn += t*(drzewo[base+r+1]-drzewo[base+r]);
        }

        cout << wyn << "xd\n";
    }

    return 0;
}

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