Submission #698396

#	Time	Username	Problem	Language	Result	Execution time	Memory
698396		Richem	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	610 ms	13200 KiB

foehn_phenomena

#include <iostream>
#define int long long
using namespace std;

const int MAX_NOMBRE = 2e5+42, MAX_FEUILLE = (1 << 18);

int nbNombre, nbReq, valMoins, valPlus;

int ab[MAX_FEUILLE*2] = {0};

int tempVent = 0;

int modifTemp(int val1, int val2) {
    return ((min((int)0, val1 - val2) * valMoins) + max((int)0, val1 - val2) * valPlus);
}

void input() {
    cin >> nbNombre >> nbReq >> valMoins >> valPlus;
    nbNombre++;

    int preced = 0;
    for(int cur = 0; cur < nbNombre; cur++) {
        cin >> ab[cur + MAX_FEUILLE];
        int valCur = ab[cur + MAX_FEUILLE];

        tempVent += modifTemp(preced, valCur);

        preced = valCur;
    }
}

int getVal(int pos) {
    pos += MAX_FEUILLE;

    int total = 0;

    for(; pos > 0; pos /= 2) {
        total += ab[pos];
    }

    return total;
}

void ajoutInter(int deb, int fin, int val) {
    deb += MAX_FEUILLE, fin += MAX_FEUILLE;

    while(deb <= fin) {
        if(deb % 2 == 1) {
            ab[deb++] += val;
        }
        if(fin % 2 == 0) {
            ab[fin--] += val;
        }

        deb /= 2; fin /= 2;
    }
}

signed main() {
    input();

    for(int req = 0; req < nbReq; req++) {
        int deb, fin, val;
        cin >> deb >> fin >> val;

        for(auto modif : {-1, 1}) {
            if(deb > 0) {
                tempVent += (modifTemp(getVal(deb-1), getVal(deb)) * modif);
            }
            if(fin+1 < nbNombre) {
                tempVent += (modifTemp(getVal(fin), getVal(fin+1)) * modif);
            }

            if(modif == -1) {
                ajoutInter(deb, fin, val);
            }
        }    

        cout << tempVent << endl;
    }
}

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