Submission #497641

#	Time	Username	Problem	Language	Result	Execution time	Memory
497641		penguin133	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	133 ms	13044 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define int long long
int ft[200005],n,q,s,t;
void update(int l, int r, int v){
	r++;
	for(;l<=n;l+=(l & -l))ft[l] += v;
	for(;r<=n;r+=(r & -r))ft[r] -= v;
}
int query(int p){
	int sum = 0;
	for(;p;p-=(p & -p))sum += ft[p];
	return sum;
}
int A[200005];
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int h,w,ans = 0;
	cin >> n >> q >> s >> t; 
	for(int i=0;i<=n;i++){
		cin >> A[i];
		if(i == 0)continue;
		if(A[i] > A[i-1])ans -= s * abs(A[i] - A[i-1]);
		else ans += t * abs(A[i] - A[i-1]);
		update(i,i,A[i]);
	}
	while(q--){
		int l,r,v;
		cin >> l>> r >> v;
		int x = query(l) - query(l-1);
		int y = 0;
		if(r < n)y = query(r+1) - query(r);
		update(l,r,v);
		int x1 = query(l) - query(l-1);
		if(x <= 0)ans -= t*(-x);
		else ans += x*s;
		if(x1 <= 0)ans -= t*x1;
		else ans -= x1*s;
		if(r != n){
			int y1 = query(r+1) - query(r);
			if(y <= 0)ans -= t*(-y);
			else ans += s*y;
			if(y1 <= 0)ans += t*(-y1);
			else ans -= s*y1;
		}
		cout << ans << '\n';
	}
}

Compilation message (stderr)

foehn_phenomena.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:18:6: warning: unused variable 'h' [-Wunused-variable]
   18 |  int h,w,ans = 0;
      |      ^
foehn_phenomena.cpp:18:8: warning: unused variable 'w' [-Wunused-variable]
   18 |  int h,w,ans = 0;
      |        ^

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