제출 #497108

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

foehn_phenomena

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

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

long long bit[MAX] ;

void add(int i , int x)
{
	++i ;
	for(; i <= n+1 ; i += (i & (-i)))
		bit[i] += x ;
}

long long get(int i)
{
	++i ;
	long long sum = 0 ;
	for(; i > 0 ; i -= (i & (-i)))
		sum += bit[i] ;
	return sum ;
}

void update(int l , int r , int x)
{
	add(l , x) , add(r+1 , -x) ;
}

long long ans = 0 ;

void upd(int idx , int sgn)
{
	if(idx == n)
		return ;
	long long x = get(idx) , y = get(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] ;
	for(int i = 0 ; i <= n ; ++i)
		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) ;
		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