제출 #497104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497104		MohamedAhmed04	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	908 ms	23288 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std ;

struct LazySegtree
{
	vector<long long>tree , lazy ;
	int sz ;
	void init(int sz2)
	{
		sz = sz2 + 2 ;
		tree = vector<long long>(sz*4 , 0) ;
		lazy = vector<long long>(sz*4 , 0) ;
	}

	long long Merge(long long x , long long y)
	{
		return max(x , y) ;
	}

	void prop(int node , int l , int r)
	{
		tree[node] += lazy[node] ;
		if(l != r)
		{
			lazy[node << 1] += lazy[node] ;
			lazy[node << 1 | 1] += lazy[node] ;
		}
		lazy[node] = 0 ;
	}

	void update(int node , int l , int r , int from , int to , int val)
	{
		prop(node , l , r) ;
		if(from > r || to < l)
			return ; 
		if(l >= from && r <= to)
		{
			lazy[node] += val ;
			prop(node , l , r) ;
			return ;
		}
		int mid = (l + r) >> 1 ;
		update(node << 1 , l , mid , from , to , val) ;
		update(node << 1 | 1 , mid+1 , r , from , to , val) ;
		tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
	}

	long long query(int node , int l , int r , int from , int to)
	{
		prop(node , l , r) ;
		if(from > r || to < l)
			return -1e18 ;
		if(l >= from && r <= to)
			return tree[node] ;
		int mid = (l + r) >> 1 ;
		auto x = query(node << 1 , l , mid , from , to) ;
		auto y = query(node << 1 | 1 , mid+1 , r , from , to) ;
		return Merge(x , y) ;
	}

	void update(int l , int r , int x)
	{
		update(1 , 0 , sz , l , r , x) ;
	}

	long long query(int l , int r)
	{
		return query(1 , 0 , sz , l , r) ; 
	}
};

const int MAX = 2e5 + 10 ;

int arr[MAX] ;
int n , q , s , t ;

long long ans = 0 ;

LazySegtree tree ;

void upd(int idx , int sgn)
{
	if(idx == n)
		return ;
	long long x = tree.query(idx , idx) , y = tree.query(idx+1 , idx+1) ;
	if(x < y)
		ans -= (y - x) * s * sgn ;
	else
		ans += (x - y) * t * sgn ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>q>>s>>t ;
	for(int i = 0 ; i <= n ; ++i)
		cin>>arr[i] ;
	tree.init(n+5) ;
	for(int i = 0 ; i <= n ; ++i)
		tree.update(i , i , arr[i]) ;
	for(int i = 0 ; i < n ; ++i)
		upd(i , 1) ;
	while(q--)
	{
		int l , r , x ;
		cin>>l>>r>>x ;
		upd(l-1 , -1) , upd(r , -1) ;
		tree.update(l , r , x) ;
		upd(l-1 , 1) , upd(r , 1) ;
		cout<<ans<<"\n" ;
	}
	return 0 ;
}		

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