Submission #1305715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305715		Tesla89	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	252 ms	12008 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define tesal ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ain(x,n) for(int i=0;i<n;i++)cin>>x[i];
#define fi first
#define se second
#define pii pair<int,int>
#define YNOut(fun) if(fun){cout<<"YES\n";}else{cout<<"NO\n";}
#define deb(arr) {for(auto i:arr){cout<<i<<' ';}cout<<'\n';}
#define int long long

using namespace std;

vector<int> seg;

void push_down(int i,int l,int r)
{
	if(l==r)return;
	seg[i<<1]+=seg[i];
	seg[i<<1|1]+=seg[i];
	seg[i]=0;
}

void build(int i,int l,int r,vector<int>&a){
	if(l==r){
		seg[i]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(i<<1,l,mid,a);
	build(i<<1|1,mid+1,r,a);
}

int query(int i,int l,int r,int k)
{
	push_down(i,l,r);
	if(l==r)return seg[i];
	int mid=l+r>>1;
	if(mid>=k)return query(i<<1,l,mid,k);
	else return query(i<<1|1,mid+1,r,k);
}

void update(int i,int l,int r,int tl,int tr,int k)
{
	if(l>tr||r<tl)return;
	if(l>=tl&&r<=tr){
		seg[i]+=k;
		return;
	}
	int mid=l+r>>1;
	update(i<<1,l,mid,tl,tr,k);
	update(i<<1|1,mid+1,r,tl,tr,k);
}

signed main()
{
    tesal;
    int n,q,s,t,wind=0,ch;
    cin>>n>>q>>s>>t;
    seg.resize((n+1)<<2,0);
    vector<int>alt(n+1);
    for(int i=0;i<=n;i++)cin>>alt[i];
    for(int i=1;i<=n;i++){
    	ch=alt[i-1]-alt[i];
    	wind+=ch*(ch<0?s:t);
    }
    build(1,0,n,alt);
    while(q--){
    	int l,r,k;
    	cin>>l>>r>>k;
    	ch=query(1,0,n,l-1)-query(1,0,n,l);
    	wind-=ch*(ch<0?s:t);
    	if(r!=n){
    		ch=query(1,0,n,r)-query(1,0,n,r+1);
    		wind-=ch*(ch<0?s:t);
    	}
    	update(1,0,n,l,r,k);
    	ch=query(1,0,n,l-1)-query(1,0,n,l);
    	wind+=ch*(ch<0?s:t);
    	if(r!=n){
    		ch=query(1,0,n,r)-query(1,0,n,r+1);
    		wind+=ch*(ch<0?s:t);
    	}
    	cout<<wind<<'\n';
    }
    return 0;
}

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