제출 #1256204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256204		nguyenphong233	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	87 ms	7236 KiB

foehn_phenomena

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,q,a[MAX],s,t,ans = 0;
int bit[MAX];
void update(int id,int val){
	if(id > n)return;
	for(;id <= n;id += id & -id)bit[id] += val;
}
int get(int id){
	int sum = 0;
	if(id == 0)return 0;
	for(;id > 0;id -= id & -id)sum += bit[id];
	return sum;
}
void uprange(int l,int r,int val){
	update(l,val);
	update(r + 1,-val);
}

signed main(){
	
	read();
	cin >> n >> q >> s >> t;
	for(int i = 0;i <= n;i++){
		cin >> a[i];
		if(i)
			uprange(i,i,a[i]);
		if(i)
			if(a[i] > a[i - 1])ans -= (a[i] - a[i - 1]) * s;
			else ans -= (a[i] - a[i - 1]) * t;
	}
	//cout << ans << '\n';
	for(int i = 1,l,r,x;i <= q;i++){
		cin >> l >> r >> x;
		int xx = get(l);
		int yy = get(l - 1);
		
		if(xx > yy){
			ans += (xx - yy) * s;
		}else{
			ans += (xx - yy) * t;
		}	
		
		xx = get(r + 1);
		yy = get(r);
		
		if(r < n){
			if(xx > yy){
				ans += (xx - yy) * s;
			}else{
				ans += (xx - yy) * t;
			}
		}
		
		uprange(l,r,x);
		xx = get(l);
		yy = get(l - 1);
		
		if(xx > yy){
			ans -= (xx - yy) * s;
		}else{
			ans -= (xx - yy) * t;
		}	
		
		xx = get(r + 1);
		yy = get(r);
		
		if(r < n){
			if(xx > yy){
				ans -= (xx - yy) * s;
			}else{
				ans -= (xx - yy) * t;
			}
		}
		
		cout << ans << '\n';
	}
}

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