제출 #1173400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173400		LucaIlie	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	114 ms	6468 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

struct AIB {
    vector<long long> aib;

    void init( int n ) {
        aib.clear();
        aib.resize( n + 1 );
    }

    void update( int i, int x ) {
        while ( i < aib.size() ) {
            aib[i] += x;
            i += (i & -i);
        }
    }    
    
    long long query( int i ) {
        long long s = 0;
        while ( i > 0 ) {
            s += aib[i];
            i -= (i & -i);
        }
        return s;
    }            
} aib;

const int MAX_N = 2e5;
int h[MAX_N + 1];
int t, s;

long long temp( int i ) {
    long long a = h[i] + aib.query( i );
    long long b = h[i + 1] + aib.query( i + 1 );
    return (long long)(a > b ? t : s) * (a - b);
}


int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );
        
    int n, q;
    
    cin >> n >> q >> s >> t;

    for ( int i = 0; i <= n; i++ )
        cin >> h[i];

    aib.init( n + 1 );

    long long ans = 0;
    for ( int i = 0; i < n; i++ )
        ans += temp( i );

    for ( int i = 0; i < q; i++ ) {
        int l, r, k;
        cin >> l >> r >> k;

        ans -= temp( l - 1 );
        if ( r < n )
            ans -= temp( r );

        aib.update( l, +k );
        aib.update( r + 1, -k ); 

        ans += temp( l - 1 );
        if ( r < n )
            ans += temp( r );
        
        cout << ans << "\n";
    }
    
    return 0;
}

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