Submission #31113

#	Time	Username	Problem	Language	Result	Execution time	Memory
31113		trath	Foehn Phenomena (JOI17_foehn_phenomena)	C++11	30 / 100	326 ms	39680 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define int long long
#define ieps 4*200010
#define eps (int) 1e9
#define pii pair<int,int>
#define clear paskdaikjdia
struct node{
	int leftmost, rightmost, sumup , sumdown;
	void clear(){
		leftmost = rightmost = sumup = sumdown = 0;
	}
} st[ieps];

int lazy[ieps]  , n , q , s , t , v[ieps] , val;

void propagate(int curr){
	if(lazy[curr]){
		st[curr].leftmost += lazy[curr];
		st[curr].rightmost += lazy[curr];
		lazy[2*curr] += lazy[curr];
		lazy[2*curr + 1] += lazy[curr];
		lazy[curr] = 0;
	}
}

node mixnode(node left, node right){
	node x;
	x.clear();
	int toadd = 0 , tosubtract = 0;
	if(left.rightmost >= right.leftmost){
		toadd += t*(left.rightmost - right.leftmost);
	}
	else if(left.rightmost < right.leftmost){
		tosubtract += s*(right.leftmost - left.rightmost);
	}
	x.leftmost = left.leftmost;
	x.rightmost = right.rightmost;
	x.sumup = left.sumup + right.sumup + toadd;
	x.sumdown = left.sumdown + right.sumdown + tosubtract;
	//cout<<x.sumup<<" "<<x.sumdown<<endl;
	return x;
}

void build(int l = 0 , int r = n- 1 , int curr = 1){
	if(l == r){
		st[curr].clear();
		st[curr].rightmost = st[curr].leftmost  = v[l];
		return;
	}
	build(l , (l+r)/2 , 2*curr);
	build((l+r)/2 + 1 , r, 2*curr + 1);
	st[curr] = mixnode(st[2*curr] , st[2*curr + 1]);
}

void update(int x , int y , int l = 0 , int r = n- 1 , int curr = 1){
	propagate(curr);
	if(l == x && r == y){
		lazy[curr]+=val;
		propagate(curr);
		return;
	}
	int mid = (l+r)/2;
	if(y <= mid){
		update(x , y, l , mid , 2*curr);
	}
	else if(x > mid){
		update(x ,y, mid + 1 ,r , 2*curr + 1);
	}
	else{
		update(x , mid , l , mid , 2*curr);
		update(mid + 1 , y , mid + 1 , r , 2*curr + 1);
	}
	propagate(2*curr);
	propagate(2*curr + 1);
	st[curr] = mixnode(st[2*curr] , st[2*curr + 1]);
}




int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	cin>>n>>q>>s>>t;
	n = n+1;
	for(int i = 0;i<n;i++) cin>>v[i];
	build();
	while(q--){
		int a, b;
		cin>>a>>b>>val;
		update(a , b);
		cout<<st[1].sumup - st[1].sumdown<<endl;
	}
}

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