Submission #516334

#	Time	Username	Problem	Language	Result	Execution time	Memory
516334		Mondeus	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	162 ms	11624 KiB

foehn_phenomena

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
const int maxn = 2e5;
long long fen[maxn+5];
long long n,q,s,t;
void update(int idx, long long v)
{
    for(int i = idx; i <= n; i += i & -i)
    {
        fen[i] += v;
    }
}
long long query(int idx)
{
    long long ans = 0;
    for(int i = idx; i > 0; i -= i & -i)
    {
        ans += fen[i];
    }
    return ans;
}
void updateRange(int l, int r, long long v)
{
    update(l,v);
    update(r+1,-v);
}
const long long MOD = 998244353;
long long ans = 0;
void solve()
{
    cin >> n >> q >> s >> t;
    for(int i = 0; i <= n; i++)
    {
        long long x;
        cin >> x;
        if(i==0) continue;
        updateRange(i,i,x);
        if(query(i-1) < x) ans -= s * (x - query(i-1));
        else ans += t * (query(i-1) - x);
    }
   // cout << ans << '\n';
    for(int i = 1; i <= q; i++)
    {
        long long l,r,x;
        cin >> l >> r >> x;
        long long old1 = query(l);
        long long old2 = query(r);
        updateRange(l,r,x);
        long long left = query(l-1);
        long long ri = query(r+1);
        if(old1 > left) ans += s * (old1 - left);
        else ans -= t * (left - old1);
        if(r != n)
        {
        if(ri > old2) ans += s * (ri - old2);
        else ans -= t * (old2 - ri);
        }
        old1 = query(l);
        old2 = query(r);
      //  cout << old1 << ' ' << old2 << '\n';
        if(old1 > left) ans -= s * (old1 - left);
        else ans += t * (left - old1);
        if(r != n)
        {
        if(ri > old2) ans -= s * (ri - old2);
        else ans += t * (old2 - ri);
        }
        cout << ans << '\n';
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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