Submission #733099

#	Time	Username	Problem	Language	Result	Execution time	Memory
733099		ac2hu	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	361 ms	15576 KiB

foehn_phenomena

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
const int N = 2e5 + 10;
int n, q, S, T, t[4*N], a[N];
void build(int v, int tl, int tr){
    if(tl == tr)t[v] = a[tl];
    else{
        int tm = (tl + tr)/2;
        build(v*2, tl, tm);
        build(v*2 + 1, tm + 1, tr);
    }
}
void update(int l, int r, int x, int v, int tl, int tr){
    if(l > r)return;
    else if(l == tl && r == tr)t[v] += x;
    else{
        int tm = (tl + tr)/2;
        update(l, min(tm, r), x, v*2, tl, tm);
        update(max(l, tm + 1), r, x, v*2+1,tm+1,tr);
    }
}
int query(int x, int v, int tl, int tr){
    if(tl == tr)return t[v];
    else{
        int tm = (tl + tr)/2;
        if(x <= tm)return t[v] + query(x, v*2,tl,tm);
        else return t[v] + query(x,v*2+1,tm+1,tr);  
    }
}
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin >> n >> q >> S >> T;
    for(int i = 0;i<=n;i++)cin >> a[i]; 
    int calc = 0;
    auto dd = [&](int a, int b, int sign){
        if(b > a)calc -= sign*(b - a)*S;
        else calc += sign*(a - b)*T; 
    };
    for(int i = 0;i<n;i++){
        dd(a[i], a[i + 1], 1);
    } 
    build(1, 0, n);
    while(q--){
        int l, r;cin >> l >> r; 
        int x;cin >> x;
        int f1 = query(l - 1, 1, 0, n), f2 = query(l, 1, 0, n);
        int s1 = query(r, 1, 0, n), s2 = query(min(r + 1, n), 1, 0, n);
        dd(f1, f2, -1);dd(s1, s2, -1);
        update(l, r, x, 1, 0, n);
        f1 = query(l - 1, 1, 0, n), f2 = query(l, 1, 0, n);
        s1 = query(r, 1, 0, n), s2 = query(min(r + 1, n), 1, 0, n);
        dd(f1, f2, 1);dd(s1, s2, 1);
        cout << calc << "\n";
    }
}

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