Submission #1009649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009649		oscar1f	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	133 ms	13652 KiB

foehn_phenomena

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

#define int long long

const int MAX_VAL=200*1000+5,DECA=(1<<18);
int nbVal,coeffDesc,coeffMont,nbReq,rep;
int arbreSom[2*DECA];

int calc(int pos) {
    int ans=0;
    pos+=DECA;
    while (pos>0) {
        ans+=arbreSom[pos];
        pos/=2;
    } 
    return ans;
}

void modif(int pos,int coeff) {
    if (pos==nbVal) {
        return;
    }
    int val1=calc(pos),val2=calc(pos+1);
    if (val1<val2) {
        rep-=coeff*(val2-val1)*coeffMont;
    }
    else {
        rep+=coeff*(val1-val2)*coeffDesc;
    }
}

void ajout(int deb,int fin,int val) {
    if (deb==fin) {
        arbreSom[deb]+=val;
    }
    else if (deb%2==1) {
        arbreSom[deb]+=val;
        ajout(deb+1,fin,val);
        return;
    }
    else if (fin%2==0) {
        arbreSom[fin]+=val;
        ajout(deb,fin-1,val);
    }
    else {
        ajout(deb/2,fin/2,val);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbVal>>nbReq>>coeffMont>>coeffDesc;
    for (int i=0;i<=nbVal;i++) {
        cin>>arbreSom[DECA+i];
    }
    for (int i=0;i<nbVal;i++) {
        modif(i,1);
    }
    int debAj,finAj,valAj;
    for (int ireq=0;ireq<nbReq;ireq++) {
        cin>>debAj>>finAj>>valAj;
        modif(debAj-1,-1);
        modif(finAj,-1);
        ajout(DECA+debAj,DECA+finAj,valAj);
        modif(debAj-1,1);
        modif(finAj,1);
        cout<<rep<<"\n";
    }
    return 0;
}

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