Submission #1039836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039836		tamir1	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	275 ms	19796 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,q,s,t,i,j,l,r,v;
ll a[200010],S[800010],lazy[800010],h1,h2,h3,h4,tmp;
void build(int node,int l,int r){
	if(l==r){
		S[node]=a[l];
		return;
	}
	int mid=(r+l)/2;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
}
void check(int node,int l,int r){
	if(lazy[node]==0) return;
	if(l==r){
		S[node]+=lazy[node];
	}
	else{
		lazy[node*2]+=lazy[node];
		lazy[node*2+1]+=lazy[node];
	}
	lazy[node]=0;
}
ll query(int node,int l,int r,int M){
	check(node,l,r);
	if(l==r) return S[node];
	int mid=(r+l)/2;
	if(M<=mid) return query(node*2,l,mid,M);
	return query(node*2+1,mid+1,r,M);
}
void update(int node,int l,int r,int L,int R,int val){
	check(node,l,r);
	if(l>R || r<L) return;
	if(l>=L && r<=R){
		lazy[node]+=val;
		return;
	}
	int mid=(r+l)/2;
	update(node*2,l,mid,L,R,val);
	update(node*2+1,mid+1,r,L,R,val);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q >> s >> t;
	for(i=0;i<=n;i++) cin >> a[i];
	for(i=0;i<n;i++){
		if(a[i]<a[i+1]) tmp-=(a[i+1]-a[i])*s;
		else tmp+=(a[i]-a[i+1])*t;
	}
	build(1,1,n);
	for(j=1;j<=q;j++){
		cin >> l >> r >> v;
		h1=(l==1 ? 0 : query(1,1,n,l-1));
		h2=query(1,1,n,l);
		h3=query(1,1,n,r);
		h4=(r==n ? h3 : query(1,1,n,r+1));
		if(h1<h2) tmp+=(h2-h1)*s;
		else tmp-=(h1-h2)*t;
		if(h3<h4) tmp+=(h4-h3)*s;
		else tmp-=(h3-h4)*t;
		update(1,1,n,l,(r<n ? r : r+1),v);
		h2=query(1,1,n,l);
		h3=query(1,1,n,r);
		if(r==n) h4=h3;
		if(h1<h2) tmp-=(h2-h1)*s;
		else tmp+=(h1-h2)*t;
		if(h3<h4) tmp-=(h4-h3)*s;
		else tmp+=(h3-h4)*t;
		cout << tmp << "\n";
	}
}

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