Submission #1075265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075265		quangminh412	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	286 ms	24040 KiB

foehn_phenomena

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

/*
  John Watson
  https://codeforces.com/profile/quangminh98

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int maxn = 2e5 + 9;
const int segsize = 4 * maxn;

int n, q, s, t;
ll a[maxn];

class SegmentTree
{
private:
	struct Node
	{
		ll sum;
		ll lazy;
		
		Node(ll sum = 0, ll lazy = 0) : sum(sum), lazy(lazy) {}
		
		Node operator + (const Node& other)
		{
			Node res;
			
			res.sum = sum + other.sum;
			res.lazy = lazy + other.lazy;
			
			return res;
		}
	};	
	
	vector<Node> st;
	int n;
	
	void build(int head, int l, int r, ll *arr)
	{
		if (l == r)
		{
			st[head] = Node(arr[l], 0);
			return;
		}
		
		int mid = l + r >> 1;
		build(2 * head, l, mid, arr);
		build(2 * head + 1, mid + 1, r, arr);
		
		st[head] = st[2 * head] + st[2 * head + 1];
	}
	
	void pass(int head, int l, int r)
	{
		if (st[head].lazy == 0) return;
		
		st[head].sum += (r - l + 1) * st[head].lazy;
		
		if (l != r)
		{
			st[2 * head].lazy += st[head].lazy;
			st[2 * head + 1].lazy += st[head].lazy;
		}
		
		st[head].lazy = 0;
	}
	
	void update(int head, int l, int r, int u, int v, ll val)
	{
		pass(head, l, r);
		if (l > v || r < u) return;
		if (u <= l && r <= v)
		{
			st[head].lazy += val;
			pass(head, l, r);
			return;
		}
		
		int mid = l + r >> 1;
		update(2 * head, l, mid, u, v, val);
		update(2 * head + 1, mid + 1, r, u, v, val);
		
		st[head] = st[2 * head] + st[2 * head + 1];
	}
	
	ll query(int head, int l, int r, int pos)
	{
		if (pos == 0) return 0;
		pass(head, l, r);
		if (l == r) return st[head].sum; 
		
		int mid = l + r >> 1;
		if (pos <= mid)
			return query(2 * head, l, mid, pos);
		return query(2 * head + 1, mid + 1, r, pos);
	}
public:
	SegmentTree(int n, ll *arr) : n(n)
	{
		st.resize(segsize);
		build(1, 1, n, arr);
	}
	
	void update(int u, int v, ll val) { return update(1, 1, n, u, v, val); }
	ll query(int pos) { return query(1, 1, n, pos); }
};

signed main()
{
	if (fopen("test.inp", "r"))
	{
		freopen("test.inp", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	faster();

	cin >> n >> q >> s >> t;
	
	ll cur = 0;
	for (int i = 0; i <= n; i++) 
	{
		cin >> a[i];
		if (i > 0) cur += (a[i - 1] - a[i]) * (a[i - 1] < a[i] ? s : t);
	}
	
	SegmentTree seg(n, a);
	
	while (q--)
	{
		int l, r; cin >> l >> r;
		ll x; cin >> x;
		
		ll pos1 = seg.query(l - 1);
		ll pos2 = seg.query(l);
		cur -= (pos1 - pos2) * (pos1 < pos2 ? s : t);
		pos2 += x;
		cur += (pos1 - pos2) * (pos1 < pos2 ? s : t);
		if (r != n)
		{
			pos1 = seg.query(r);
			pos2 = seg.query(r + 1);
			cur -= (pos1 - pos2) * (pos1 < pos2 ? s : t);
			pos1 += x;
			cur += (pos1 - pos2) * (pos1 < pos2 ? s : t);
		}
		seg.update(l, r, x);
		
		cout << cur << '\n';
	}

	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In member function 'void SegmentTree::build(int, int, int, long long int*)':
foehn_phenomena.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l + r >> 1;
      |             ~~^~~
foehn_phenomena.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, long long int)':
foehn_phenomena.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   int mid = l + r >> 1;
      |             ~~^~~
foehn_phenomena.cpp: In member function 'long long int SegmentTree::query(int, int, int, int)':
foehn_phenomena.cpp:98:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |   int mid = l + r >> 1;
      |             ~~^~~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:118:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   freopen("test.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:119:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   freopen("test.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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