Submission #232729

#	Time	Username	Problem	Language	Result	Execution time	Memory
232729		jiahng	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	161 ms	9208 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define maxn 200101
#define int ll
int N,Q,S,T;
int fw[maxn],A[maxn];

void update(int p,int v){ //update position p by +=v
	for (int i=p; i<=N+10; i+= (i&(-i))){
		fw[i] += v;
	}
}

void upd(int a,int b, int c){ //update position a to b by +=c
	update(a,c); //upd function from the PURQ fenwick
	update(b+1,-c);
}

int qry(int p){ //query p
	int ans = 0;
	for (int i = p; i>0; i -= (i&(-i))){
		ans += fw[i];
	}
	return ans;
}

int32_t main(){
	fast;
	
	cin>>N>>Q>>S>>T;
	
	FOR(i,0,N){
		cin>>A[i]; if (i != 0) upd(i,i,A[i]);
	}
	
	int cur = 0;
	FOR(i,0,N-1){
		if (A[i] < A[i+1]) cur -= S * (A[i+1] - A[i]);
		else cur += T * (A[i] - A[i+1]);
	}
	
	FOR(i,1,Q){
		int a,b,c;
		cin>>a>>b>>c;
		
		int Aval = qry(a);
		int Aprev = qry(a-1);
		int Bval = qry(b);
		
		
		if (Aprev < Aval) cur += S * (Aval - Aprev);
		else cur -= T * (Aprev - Aval);
		
		Aval += c;
		
		if (Aprev < Aval) cur -= S * (Aval - Aprev);
		else cur += T * (Aprev - Aval);
		
		if (b+1 <= N){
			int Bnext = qry(b+1);
			if (Bval < Bnext) cur += S * (Bnext - Bval);
			else cur -= T * (Bval - Bnext);
			Bval += c;
			if (Bval < Bnext) cur -= S * (Bnext - Bval);
			else cur += T * (Bval - Bnext);
		}
		cout<<cur<<'\n';
		upd(a,b,c);
	}
	
		
}

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