Submission #879613

#	Time	Username	Problem	Language	Result	Execution time	Memory
879613		iskhakkutbilim	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	416 ms	14508 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
// Tazhibaev Iskhak
// call me, if scholarship $$ is at least ELON_MUSK_MAX
#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 inv_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);
	}
}


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;
		if(r + 1 <= n) inv_degree(r+1);
		inv_degree(l);
		add(l, r, x, 1, 1, n);
		if(r+1 <= n){
			degree(r+1);
		}
		degree(l);	
		cout << sum << '\n';
	}
	
	return 0;
}

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