Submission #383168

#	Time	Username	Problem	Language	Result	Execution time	Memory
383168		MODDI	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	980 ms	35048 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, q, s, t;
vi arr;
class klas{
	public:
		ll l;
		ll r;
		ll temp;
};
vector<klas> tree(4 * 200000);
ll lazy[4 * 200000];
void build(int node, int l, int r){
	if(l == r){
		//cout<<l<<endl;
		if(l == n + 1)	return;
		klas cur;
		cur.l = arr[l];
		cur.r = arr[l];
		cur.temp = 0;
		tree[node] = cur;
	}
	else{
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);
		klas next;
		next.l = tree[node * 2].l;
		next.r = tree[node * 2 + 1].r;
		next.temp =tree[node * 2].temp + tree[node * 2 + 1].temp;
		if(tree[node * 2].r < tree[node * 2 + 1].l){
			ll diff = tree[node * 2 + 1].l - tree[node * 2].r;
			next.temp= next.temp - diff * s;
			//cout<<tree[node * 2 + 1].l <<" "<<tree[node * 2].r<<endl;
		}
		else if(tree[node * 2].r > tree[node * 2  + 1].l){
			ll diff = tree[node * 2].r - tree[node * 2 + 1].l;
			next.temp = next.temp + diff * t;
			//cout<<tree[node * 2 + 1].l <<" "<<tree[node * 2].r<<endl;
		}
		tree[node] = next;
 	}
}
/*void update(int node, int l, int r, int pos, int x){
	if(l == r && l == pos)
	{
		tree[node].l += x;
		tree[node].r += x;
	}
	else{
		int mid = (l + r) / 2;
		if(pos <= mid)
			update(node * 2, l, mid, pos, x);
		else
			update(node * 2 + 1, mid + 1, r, pos, x);
			
		klas next;
		next.l = tree[node * 2].l;
		next.r = tree[node * 2 + 1].r;
		next.temp =tree[node * 2].temp + tree[node * 2 + 1].temp;
		if(tree[node * 2].r < tree[node * 2 + 1].l){
			int diff = tree[node * 2 + 1].l - tree[node * 2].r;
			next.temp= next.temp - diff * s;
			//cout<<tree[node * 2 + 1].l <<" "<<tree[node * 2].r<<endl;
		}
		else if(tree[node * 2].r > tree[node * 2  + 1].l){
			int diff = tree[node * 2].r - tree[node * 2 + 1].l;
			next.temp = next.temp + diff * t;
			//cout<<tree[node * 2 + 1].l <<" "<<tree[node * 2].r<<endl;
		}
		tree[node] = next;
	}
}*/
void update(int node, int l, int r, int L, int R, int x){
	if(lazy[node] != 0){
		tree[node].l += lazy[node];
		tree[node].r += lazy[node];
		if(l != r){
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
	if(r < L || R < l)	return;
	if(L <= l && r <= R){
		tree[node].l += x;
		tree[node].r += x;
		if(l != r){
			lazy[node * 2] += x;
			lazy[node * 2 + 1] += x;
		}
		return;
	}
	int mid = (l + r) / 2;
	update(node * 2, l, mid, L, R, x);
	update(node * 2 + 1, mid + 1, r, L, R, x);
	klas next;
	next.l = tree[node * 2].l;
	next.r = tree[node * 2 + 1].r;
	next.temp = tree[node * 2].temp + tree[node * 2 + 1].temp;
	if(tree[node * 2].r < tree[node * 2 + 1].l){
		ll diff = tree[node * 2 + 1].l - tree[node * 2].r;
		next.temp= next.temp - diff * s;
		//cout<<diff<<" "<<tree[node * 2].r<<" "<<tree[node * 2 + 1].l<<endl;
		//cout<<tree[node * 2 + 1].l <<" "<<tree[node * 2].r<<endl;
	}
	else if(tree[node * 2].r > tree[node * 2  + 1].l){
		ll diff = tree[node * 2].r - tree[node * 2 + 1].l;
		next.temp = next.temp + diff * t;
		//cout<<diff<<" "<<tree[node * 2].r<<" "<<tree[node * 2 + 1].l<<endl;
		//cout<<tree[node * 2 + 1].l <<" "<<tree[node * 2].r<<endl;
	}
	tree[node] = next;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(lazy, 0, sizeof(lazy));
	cin>>n>>q>>s>>t;
	for(int i = 0; i <=n; i++){
		int a;
		cin>>a;
		arr.pb(a);
	}
	build(1, 0, n);
	//cout<<tree[1].temp<<endl;
	while(q--){
		int a, b, x;
		cin>>a>>b>>x;
		update(1, 0, n, a, b, x);
		cout<<tree[1].temp<<endl;
	}
}

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