제출 #1278926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278926		SSKMF	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	203 ms	19880 KiB

foehn_phenomena

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

struct Nod {
    int64_t inceput , sfarsit , suma[2] , lazy;
} arbore[400002];

inline Nod Combina (Nod& stanga , Nod& dreapta)
{
    Nod rezultat;
    rezultat.inceput = stanga.inceput;
    rezultat.sfarsit = dreapta.sfarsit;
    rezultat.suma[0] = stanga.suma[0] + dreapta.suma[0] + max(dreapta.inceput - stanga.sfarsit , (int64_t)0);
    rezultat.suma[1] = stanga.suma[1] + dreapta.suma[1] + max(stanga.sfarsit - dreapta.inceput , (int64_t)0);
    rezultat.lazy = 0;
    return rezultat;
}

inline void Lazy_Update (const int nod , const int stanga , const int dreapta)
{
    if (!arbore[nod].lazy)
        { return; }

    if (stanga != dreapta)
    {
        const int mijloc = (stanga + dreapta) >> 1;
        arbore[nod + ((mijloc - stanga + 1) << 1)].lazy += arbore[nod].lazy;
        arbore[nod + 1].lazy += arbore[nod].lazy;
    }

    arbore[nod].inceput += arbore[nod].lazy;
    arbore[nod].sfarsit += arbore[nod].lazy;
    arbore[nod].lazy = 0;
}

inline void Build (const int nod , const int stanga , const int dreapta)
{
    if (stanga == dreapta)
    {
        int valoare;
        cin >> valoare;
        arbore[nod].inceput = arbore[nod].sfarsit = valoare;
        return;
    }

    const int mijloc = (stanga + dreapta) >> 1;
    Build(nod + 1 , stanga , mijloc);
    Build(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta);
    arbore[nod] = Combina(arbore[nod + 1] , arbore[nod + ((mijloc - stanga + 1) << 1)]);
}

inline void Update (const int nod , const int stanga , const int dreapta , const int stanga_update , const int dreapta_update , const int valoare)
{
    Lazy_Update(nod , stanga , dreapta);

    if (dreapta_update < stanga || dreapta < stanga_update)
        { return; }

    if (stanga_update <= stanga && dreapta <= dreapta_update)
        { arbore[nod].lazy = valoare; Lazy_Update(nod , stanga , dreapta); return; }
        
    const int mijloc = (stanga + dreapta) >> 1;
    Update(nod + 1 , stanga , mijloc , stanga_update , dreapta_update , valoare);
    Update(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , stanga_update , dreapta_update , valoare);
    arbore[nod] = Combina(arbore[nod + 1] , arbore[nod + ((mijloc - stanga + 1) << 1)]);
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int limita , numar_operatii , factor_1 , factor_2;
    cin >> limita >> numar_operatii >> factor_1 >> factor_2;

    Build(1 , 0 , limita);
    while (numar_operatii--)
    {
        int stanga , dreapta , termen;
        cin >> stanga >> dreapta >> termen;

        Update(1 , 0 , limita , stanga , dreapta , termen);
        
        cout << arbore[1].suma[1] * factor_2 - arbore[1].suma[0] * factor_1 << '\n';
    }

    return 0;
}

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