Submission #1181513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181513		inesfi	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	112 ms	8984 KiB

foehn_phenomena

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

#define endl "\n"
#define int long long

const int TAILLEMAXI=(1<<19);
int h[TAILLEMAXI];
int arbre[TAILLEMAXI];
int S,T,DECA;

int change(int a,int b){
    if (a<=b){
        return S*(a-b);
    }
    return T*(a-b);
}

void ajouter(int a,int b,int v){
    if (a==b){
        arbre[a]+=v;
        return ;
    }
    if (a%2==1){
        arbre[a]+=v;
        ajouter(a+1,b,v);
        return ;
    }
    if (b%2==0){
        arbre[b]+=v;
        ajouter(a,b-1,v);
        return ;
    }
    ajouter(a/2,b/2,v);
}

int trouver(int a){
    if (a==0){
        return arbre[a];
    }
    return arbre[a]+trouver(a/2);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int nbnb,nbquest;
    cin>>nbnb>>nbquest>>S>>T;
    DECA=(1<<18);
    int rep=0;
    for (int i=0;i<nbnb+1;i++){
        cin>>h[i];
        if (i!=0){
            rep+=change(h[i-1],h[i]);
            //cout<<change(h[i-1],h[i])<<endl;
        }
    }
    //cout<<rep<<endl;
    for (int iquest=0;iquest<nbquest;iquest++){
        int deb,fin,val;
        cin>>deb>>fin>>val;
        int deb1,deb2,fin1,fin2;
        deb1=trouver(deb-1+DECA)+h[deb-1];
        deb2=trouver(deb+DECA)+h[deb];
        rep-=change(deb1,deb2);
        rep+=change(deb1,deb2+val);
        if (fin!=nbnb){
            fin1=trouver(fin+DECA)+h[fin];
            fin2=trouver(fin+1+DECA)+h[fin+1];
            rep-=change(fin1,fin2);
            //cout<<change(fin1,fin2)<<endl;
            rep+=change(fin1+val,fin2);
            //cout<<change(fin1+val,fin2)<<endl;
        }
        //cout<<deb1<<" "<<deb2<<" "<<fin1<<" "<<fin2<<endl;
        cout<<rep<<endl;
        ajouter(deb+DECA,fin+DECA,val);
    }
    return 0;
}

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