제출 #879601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879601		iskhakkutbilim	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	30 / 100	1056 ms	12884 KiB

foehn_phenomena

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

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
const int N = 2e5;

int n, q, S, T;
int lazy[4*N], t[4*N];
int a[N+10];
void push(int v, int vl, int vr){
	if(!lazy[v]) return;
	t[v]+= (lazy[v] * (vr-vl+1));
	if(vl != vr){
		lazy[v<<1]+= lazy[v];
		lazy[v<<1|1]+= lazy[v];	
	}
	lazy[v] = 0;
}

void add(int l, int r, int x, int v, int vl, int vr){
	push(v, vl, vr);
	if(l > vr or vl > r) return;
	if(l <= vl && r >= vr){
		lazy[v]+= x;
		push(v, vl, vr);
		return;
	}
	int mid = (vl + vr)>>1;
	add(l, r, x, v<<1, vl, mid);
	add(l, r, x, v<<1|1, mid+1, vr);
}

int get(int pos, int v, int vl, int vr){
	push(v, vl, vr);
	if(vl == vr) return t[v];
	int mid = (vl + vr)>>1;
	if(mid >= pos) return get(pos, v<<1, vl, mid);
	else return get(pos, v<<1|1, mid+1, vr);
}

int sum;
void degree(int idx){
	int A;
	int B = get(idx, 1, 1, n);
	if(idx == 1) A = 0;
	else A = get(idx-1, 1, 1, n);
	if(B > A){
		sum-= S * abs(B-A);
	}else{
		sum+= T * abs(B-A);
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q >> S >> T;
	for(int i = 0;i <= n; i++){
		cin >> a[i];
		add(i, i, a[i], 1, 1, n);
	}
	for(int i = 1;i <= n; i++){
		degree(i);
	}
	
	while(q--){
		int l, r, x; cin >> l >> r >> x;
		add(l, r, x, 1, 1, n);
		sum = 0;
		for(int i = 1;i <= n; i++){
			degree(i);
		}
		
		cout << sum << '\n';
	}
	
	return 0;
}

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