Submission #492875

#	Time	Username	Problem	Language	Result	Execution time	Memory
492875		PoPularPlusPlus	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	315 ms	15472 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

ll val[500003];

void aos(int l , int r , ll c , int x , int lx , int rx){
	if(lx >= l && rx <= r){
		val[x] += c;
		return;
	}
	if(r <= lx || l >= rx)return;
	int m = (lx + rx)/2;
	val[2 * x + 1] += val[x];
	val[2 * x + 2] += val[x];
	aos(l ,r , c , 2 * x + 1 , lx , m);
	aos(l , r , c , 2 * x + 2 ,  m, rx);
}

ll find(int i , int x , int lx , int rx){
	if(rx - lx == 1)return val[x];
	int m = (lx + rx)/2;
	val[2 * x + 1] += val[x];
	val[2 * x + 2] += val[x];
	val[x] = 0;
	if(i < m){
		return find(i , 2 * x + 1 , lx , m);
	}
	else return find(i , 2 * x + 2 , m , rx);
}

void solve(){
	ll n , q , s , t;
	cin >> n >> q >> s >> t;
	int siz = 1;
	while(siz < n)siz*=2;
    memset(val,0,sizeof val);
	ll arr[n + 1];
	for(int i = 0; i <= n; i++)cin >> arr[i];
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		if(arr[i-1] < arr[i]){
			ans -= (arr[i] - arr[i-1]) * s;
		}
		else ans += (arr[i-1] - arr[i]) * t;
	}
	while(q--){
		int l, r;
		ll x;
		cin >> l >> r >> x;
		ll curl = arr[l] + find(l , 0 , 0 , siz);
		ll curr = arr[r] + find(r , 0 , 0 , siz);
		ll pre , next;
		if(l == 1)pre = 0;	
		else pre = arr[l-1] + find(l - 1 , 0 , 0, siz);
		if(r == n)next = 1e18;
		else next = arr[r + 1] + find(r + 1 , 0 , 0 , siz);
		if(curl > pre)ans += (curl - pre) * s;
		else ans -= (pre - curl) * t;
		if(next != 1e18){
			if(next > curr)ans += (next - curr) * s;
			else ans -= (curr-  next) * t;
		}
		aos(l , r + 1 , x , 0 , 0 , siz);
		curl += x;
		curr += x;
		if(curl > pre)ans -= (curl - pre) * s;
		else ans += (pre - curl) * t;
		if(next != 1e18){
			if(next > curr)ans -= (next - curr) * s;
			else ans += (curr-  next) * t;
		}
		cout << ans << '\n';
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

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