Submission #736308

#	Time	Username	Problem	Language	Result	Execution time	Memory
736308		LCJLY	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	655 ms	42816 KiB

foehn_phenomena

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

#define int long long 
typedef pair<int,int>pii;

inline int combine(int a, int b){
	return a+b;
}

const int defval=0;

#define lazyChange (e-s+1)

struct node{
	int s,e,m;
	node *l, *r;
	int v;
	int lazyUpd, lazySet;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(defval),lazyUpd(0){
		if(s!=e){
			l=new node(s,m); r=new node(m+1,e);
		}
	}
	
	inline int forceProp(){
		if(s==e){
			v+=lazyUpd; lazyUpd=0; return v;
		}
		if(lazyUpd!=0){
			v+=lazyChange*lazyUpd,l->lazyUpd+=lazyUpd,r->lazyUpd+=lazyUpd,lazyUpd=0;
		}
		return v;
	}
	
	void rangeUpd(int first, int last, int c){
		if(first<=s&&last>=e){
			lazyUpd+=c;
			return;
		}
		forceProp();
		if(first<=m)l->rangeUpd(first,last,c);
		if(last>m)r->rangeUpd(first,last,c);
		v=combine(l->forceProp(),r->forceProp());
	}
	
	int query(int x, int y){
		if(s==e){
			v+=lazyUpd;
			lazyUpd=0;
			return v;
		}
		if(x<=s&&y>=e){
			forceProp();
			return v;
		}
		forceProp();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,q,s,t;
	cin >> n >> q >> s >> t;
	
	node st(0,n+5);
	//node ans(0,n+5);
	int ans[n+5];
	memset(ans,0,sizeof(ans));
	
	for(int x=0;x<=n;x++){
		int temp;
		cin >> temp;
		st.rangeUpd(x,x,temp);
	}
	
	int counter=0;
	for(int x=1;x<=n;x++){
		int hold=st.query(x,x);
		int hold2=st.query(x-1,x-1);
		if(hold2<hold){
			//ans.rangeUpd(x,x,-1LL*s*abs(hold-hold2));
			ans[x]=-1LL*s*abs(hold-hold2);
		}
		else{
			//ans.rangeUpd(x,x,t*abs(hold-hold2));
			ans[x]=t*abs(hold-hold2);
		}
		counter+=ans[x];
	}
	
	int l,r,val;
	for(int x=0;x<q;x++){
		cin >> l >> r >> val;
		
		st.rangeUpd(l,r,val);
		
		//changes 
		//left
		//int hold=ans.query(l,l);
		int hold2=st.query(l,l);
		int hold3=st.query(l-1,l-1);
		
		if(hold3<hold2){
			//ans.rangeUpd(l,l,-hold-1LL*s*abs(hold2-hold3));
			counter-=ans[l];
			ans[l]=-1LL*s*abs(hold2-hold3);
			counter+=ans[l];
		}
		else{
			//ans.rangeUpd(l,l,-hold+t*abs(hold2-hold3));
			counter-=ans[l];
			ans[l]=t*abs(hold2-hold3);
			counter+=ans[l];
		}
		
		if(r!=n){
			int hold4=st.query(r,r);
			int hold5=st.query(r+1,r+1);
			//int hold6=ans.query(r+1,r+1);
			if(hold4<hold5){
				//ans.rangeUpd(r+1,r+1,-hold6-1LL*s*abs(hold4-hold5));
				counter-=ans[r+1];
				ans[r+1]=-1LL*s*abs(hold4-hold5);
				counter+=ans[r+1];
			}
			else{
				//ans.rangeUpd(r+1,r+1,-hold6+t*abs(hold4-hold5));
				counter-=ans[r+1];
				ans[r+1]=t*abs(hold4-hold5);
				counter+=ans[r+1];
			}
		}
		
		//cout << ans.query(0,n) << "\n";
		cout << counter << "\n";
	}
}

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