Submission #1179558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179558		Szymon_Pilipczuk	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	96 ms	7236 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
int n,q,s,t;
long long tr[400002];
void add(int l, int r, int v)
{
    l+=n+1;
    r+=n+1;
    tr[l]+=v;
    if(r!=l) tr[r]+=v;
    while(l/2 != r/2)
    {
        if(l%2 == 0) tr[l+1] +=v;
        if(r%2 == 1) tr[r-1] +=v;
        l/=2;r/=2;
    }
}
long long check(int p)
{
    long long ans = 0;
    p+=n+1;
    while(p > 0)
    {
        ans+=tr[p];
        p/=2;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q>>s>>t;
    long long ans= 0;
    for(int i = 0;i<n+1;i++)
    {
        long long a;
        cin>>a;
        add(i,i,a);
        if(i!= 0)
        {
            long long c = check(i-1);
            if(a > c)
            {
                ans -= (a-c)*s;
            }
            else
            {
                ans+= (c-a)*t;
            }
        }
    }
    for(int i = 0;i<q;i++)
    {

        int l,r,x;
        cin>>l>>r>>x;
        long long a = check(l-1);
        long long b =check(l);
        long long f,g;
        if(r!=n)
        {
            f = check(r);
            g = check(r+1);
        }

        add(l,r,x);
        long long c = check(l);
        long long h = check(r);
        ans += (min(a,b) - min(a,c))*t;
        ans += (max(a,b) - max(a,c))*s;
        if(r!= n)
        {
            ans-=(min(g,f) - min(g,h))*s;
            ans-=(max(g,f) - max(g,h))*t;
        }
        cout<<ans<<"\n";


    }


}

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