Submission #332024

#	Time	Username	Problem	Language	Result	Execution time	Memory
332024		Atill83	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	422 ms	26860 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, q, s, T;
ll a[MAXN];
struct node{
    ll lazy, val, left, right;
} t[4*MAXN];

void build(int v, int tl, int tr){
    if(tl == tr)
        t[v] = {0, 0, a[tl], a[tl]};
    else{
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm + 1, tr);

        t[v].left = t[2*v].left;
        t[v].right = t[2*v + 1].right;
        t[v].lazy = 0;
        t[v].val = t[2*v].val + (t[2*v].right >= t[2*v + 1].left ? T : -s)*abs(t[2*v].right - t[2*v + 1].left) + t[2*v + 1].val;
    }
}

void push(int v){
    ll lz = t[v].lazy;
    t[v].lazy = 0;
    if(!lz) return;
    t[2*v].left += lz;
    t[2*v + 1].left += lz;
    t[2*v].right += lz;
    t[2*v + 1].right += lz;
    t[2*v].lazy += lz;
    t[2*v + 1].lazy += lz;
}

void upd(int v, int tl, int tr, int l, int r, ll val){
    if(l > r) return;
    if(tl == l && tr == r){
        t[v].left += val;
        t[v].right += val;
        t[v].lazy += val;
    }else{
        push(v);
        int tm = (tl + tr) / 2;
        upd(2*v, tl, tm, l, min(tm, r), val);
        upd(2*v + 1, tm + 1, tr, max(tm + 1, l), r, val);
        t[v].left = t[2*v].left;
        t[v].right = t[2*v + 1].right;
        t[v].lazy = 0;
        t[v].val = t[2*v].val + (t[2*v].right >= t[2*v + 1].left ? T : -s)*abs(t[2*v].right - t[2*v + 1].left) + t[2*v + 1].val;
    }
}




int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>q>>s>>T;

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

    build(1, 0, n);

    while(q--){
        int l, r, x;
        cin>>l>>r>>x;
        upd(1, 0, n, l, r, x);
        cout<<t[1].val<<endl;
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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