Submission #1302467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302467		ffeyyaae_	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	112 ms	7356 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e5+5;

int n, q;
ll S, T, ans;
ll a[N];

struct FWtree
{
    ll tree[N];

    void update( int idx, ll v )
    {
        for( int i=idx;i<=n;i+=i&-i ) tree[i] += v;
    }

    ll query( int idx )
    {
        ll sum = 0;
        for( int i=idx;i>0;i-=i&-i ) sum += tree[i];
        return sum;
    }

}fen;

ll cal( ll a, ll b )
{
    return (a-b)*((a>b)?T:S);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> q >> S >> T;
    for( int i=0;i<=n;i++ )
    {
        cin >> a[i];
        if(i>0) fen.update( i, a[i]-a[i-1] );
        if(i>0) ans += cal( a[i-1], a[i] );
    }
    while( q-- )
    {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        ll a = cal( fen.query(l-1), fen.query(l) );
        if( r<n ) a += cal( fen.query(r), fen.query(r+1) );
        fen.update( l, x );
        fen.update( r+1, -x );
        ll b = cal( fen.query(l-1), fen.query(l) );
        if( r<n ) b += cal( fen.query(r), fen.query(r+1) );
        ans += b-a;
        cout << ans << "\n";
    }
    return 0;
}

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