제출 #1143699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143699		ezzzay	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	129 ms	8924 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
#define endl '\n'
const int N=2e5+5;
int a[N];
vector<int>ans;
int bit[N];
void update(int idx, int val){
    while(idx<N){
        bit[idx]+=val;
        idx+= idx & -idx;
    }
}
int find(int idx){
    int s=0;
    while(idx>0){
        s+=bit[idx];
        idx-= idx & -idx;
    }
    return s;
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,q,s,t;
	cin>>n>>q>>s>>t;
	for(int i=0;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
	    update(i,a[i]);
	    update(i+1,-a[i]);
	}
	int h=0;
	for(int i=1;i<=n;i++){
		int e=find(i),f=find(i-1);
		if(e>f)h-=s*abs(e-f);
		else h+=t*abs(e-f);
	}
	while(q--){
		int l,r,x;
		cin>>l>>r>>x;
		if(find(l)>find(l-1)){
			h+=s*abs(find(l)-find(l-1));
		}
		else{
			h-=t*abs(find(l)-find(l-1));
		}
		if(r!=n){
		    if(find(r+1)>find(r)){
    			h+=s*abs(find(r+1)-find(r));
    		}
    		else{
    			h-=t*abs(find(r+1)-find(r));
    		}
		}
		
		update(l,x);
		update(r+1,-x);
		
		
		
		if(find(l)>find(l-1)){
			h-=s*abs(find(l)-find(l-1));
		}
		else{
			h+=t*abs(find(l)-find(l-1));
		}
		if(r!=n){
		    if(find(r+1)>find(r)){
    			h-=s*abs(find(r+1)-find(r));
    		}
    		else{
    			h+=t*abs(find(r+1)-find(r));
    		}
		}
		
		
		ans.pb(h);
	}
	for(auto a:ans)cout<<a<<endl;
}

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