제출 #698396

#제출 시각아이디문제언어결과실행 시간메모리
698396RichemFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
610 ms13200 KiB
#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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...