Submission #151608

#	Time	Username	Problem	Language	Result	Execution time	Memory
151608		blue	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	30 / 100	1051 ms	22888 KiB

foehn_phenomena

#include <iostream>
#include <vector>
using namespace std;

long long N, Q, S, T;
long long* A;

class segtree
{
    public:
    long long v;
    long long l;
    long long r;
    
    segtree* left;
    segtree* right;
    
    segtree(long long L, long long R)
    {
        l = L;
        r = R;
        if(L == R)
        {
            left = right = NULL;
            v = A[l];
        }
        else
        {
            left = new segtree(L, (L+R)/2);
            right = new segtree((L+R)/2 + 1, R);
            v = 0;
        }
    }
    
    void update(long long L, long long R, long long U)
    {
        if(R < l || r < L) return;
        if(L <= l && r <= R) v += U;
        else
        {
            left->update(L, R, U);
            right->update(L, R, U);
        }
    }
    
    long long val(long long I)
    {
        if(I == 0) return 0;
        if(l == r) return v;
        return v + ((I <= (l+r)/2) ? left->val(I) : right->val(I));
    }
};

int main()
{
    cin >> N >> Q >> S >> T;
    A = new long long[N+1];
    for(long long i = 0; i <= N; i++) cin >> A[i];
    
    segtree B(1, N);
    
    long long w = 0;
    for(long long i = 1; i <= N; i++) w += (A[i-1] - A[i]) * (A[i-1] < A[i] ? S:T);
    
    long long l, r, u;
    
    vector<long long> res;
    for(long long i = 1; i <= Q; i++)
    {
        cin >> l >> r >> u;
        w -= (B.val(l-1) - B.val(l)) * (B.val(l-1) < B.val(l) ? S:T);
        if(r != N) w -= (B.val(r) - B.val(r+1)) * (B.val(r) < B.val(r+1) ? S:T);
        B.update(l, r, u);
        w += (B.val(l-1) - B.val(l)) * (B.val(l-1) < B.val(l) ? S:T);
        if(r != N) w += (B.val(r) - B.val(r+1)) * (B.val(r) < B.val(r+1) ? S:T);
        
        res.push_back(w);
    }
    for(long long r:res) cout << r << '\n';
    
    return 0;
}

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