제출 #532522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532522		Marceantasy	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	373 ms	35072 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std; 

#define ll long long 
#define ar array

typedef pair<int, int> pi;

const int mxN = 2e5+5, M = 1e9+7;
ll n, q, s, t; 

struct SEG{
    ll ans[4*mxN], rval[4*mxN], lval[4*mxN], lazy[4*mxN];
    void init(){
        memset(ans, 0, sizeof(ans));
        memset(rval, 0, sizeof(rval)); 
        memset(lval, 0, sizeof(lval));
        memset(lazy, 0, sizeof(lazy));
    }
    void push(int i){
        rval[2*i] += lazy[i];
        lval[2*i] += lazy[i];
        lazy[2*i] += lazy[i];
        rval[2*i+1] += lazy[i];
        lval[2*i+1] += lazy[i];
        lazy[2*i+1] += lazy[i];
        lazy[i] = 0;
    }
    void merge(int i){
        rval[i] = rval[2*i+1];
        lval[i] = lval[2*i];    
        ans[i] = ans[2*i] + ans[2*i+1];
        if(rval[2*i] < lval[2*i+1]){
            ans[i] += s*(lval[2*i+1]-rval[2*i]);
        }else{
            ans[i] -= t*(rval[2*i]-lval[2*i+1]);
        }
    }
    void upd(int l1, int r1, int l2, int r2, int i, ll val){
        if(r1 < l2 || r2 < l1) return;
        if(l1 <= l2 && r2 <= r1){
            rval[i]+=val;
            lval[i]+=val;
            lazy[i]+=val;
            return;
        }
        int m2 = (l2+r2)/2;
        push(i);
        upd(l1, r1, l2, m2, 2*i, val);
        upd(l1, r1, m2+1, r2, 2*i+1, val);
        merge(i);
    }
    void print(int l1, int r1, int i){
        if(l1 == r1){
            cout << lval[i] << " ";
            return;
        }
        int m1 = (l1+r1)/2;
        print(l1, m1, 2*i);
        print(m1+1, r1, 2*i+1);
    }
}seg;

int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    cin >> n >> q >> s >> t;
    seg.init();
    //seg.print(0, n, 1);
    //cout << " here\n";
    for(int i = 0; i<=n; ++i){
        ll x; 
        cin >> x;
        seg.upd(i, i, 0, n, 1, x);
    }
    //seg.print(0, n, 1);
    //cout << "\n";
    while(q--){
        int a, b;
        ll c;  
        cin >> a >> b >> c; 
        seg.upd(a, b, 0, n, 1, c);
      //  seg.print(0, n, 1);
      //  cout << "\n";
        cout << -seg.ans[1] << "\n";
    }
}

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