Submission #129322

#	Time	Username	Problem	Language	Result	Execution time	Memory
129322		AuldLangSyne	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	632 ms	13824 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define ll long long
#define f(i, a, b) for(ll i = a; i <= b; ++i)
#define ff(i, a, b) for(ll i = a; i < b; ++i)
#define F(i, a, b) for(ll i = a; i >= b; --i)
#define FF(i, a, b) for(ll i = a; i > b; --i)
#define x first
#define y second
#define X real()
#define Y imag()
using namespace std;
typedef complex<ll> P;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;

const ll INF = 1e9+7;
const ll N = 2e5+7;
ll n, m, R, S, u, v, o, node[4*N], lazy[4*N], a[N];

void build(ll id, ll l, ll r){
	if(l == r){
		node[id] = (a[r] > a[r-1] ? S*(a[r-1] - a[r]) : R*(a[r-1] - a[r]));
		return;
	}
	ll mid = (l+r)/2;
	build(2*id, l, mid);
	build(2*id+1, mid+1, r);
	node[id] = node[2*id] + node[2*id+1];
}
void down(ll id){
	if(!lazy[id]) return;
	lazy[2*id] += lazy[id];
	lazy[2*id+1] += lazy[id];
	lazy[id] = 0;
}
void upd(ll id, ll l, ll r, ll u, ll v, ll val){
	if(v < l || r < u) return;
	if(u <= l && r <= v){
		lazy[id] += val;
		return;
	}
	int mid = (l+r)/2;
	down(id);
	upd(2*id, l, mid, u, v, val);
	upd(2*id+1, mid+1, r, u, v, val);
}

ll get_point(ll id, ll l, ll r, ll post){
	if(post < l || r < post) return INF;
	if(l == r){
		return a[r] + lazy[id];
	}
	ll mid = (l+r)/2;
	down(id);
	return min(get_point(2*id, l, mid, post), get_point(2*id+1, mid+1, r, post));
}

void upd_point(ll id, ll l, ll r, ll post){
	if(post < l || r < post) return;
	if(l == r){
		if(post > 1) u = get_point(1,1,n,post-1);
		else u = 0;
		node[id] = (a[r] + lazy[id] > u ? S*(u - a[r] - lazy[id]) : R*(u - a[r] - lazy[id]));
		return;
 	}
 	ll mid = (l+r)/2;
 	down(id);
 	upd_point(2*id, l, mid, post);
 	upd_point(2*id+1, mid+1, r, post);
 	node[id] = node[id*2] + node[id*2+1];
}
signed main(){
	scanf("%lld %lld %lld %lld", &n, &m, &S, &R);
	f(i,0,n){
		scanf("%lld", &a[i]);
	}
	build(1,1,n);
	while(m--){
		scanf("%lld %lld %lld", &u, &v, &o);
		upd(1,1,n,u,v,o);
		if(u > 0) upd_point(1,1,n,u);
		if(v < n) upd_point(1,1,n,v+1);
		printf("%lld\n", node[1]);
	}
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld", &n, &m, &S, &R);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
   ~~~~~^~~~~~~~~~~~~~~
foehn_phenomena.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld", &u, &v, &o);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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