oj.uz

답안 #813280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
813280 2023-08-07T14:58:57 Z tlnk07 Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 1 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
 
long long n, q, a[200001];
pair<int, pair<int, int>> tree[1000001];
 
void build(int id, int l, int r)
{
	if(l == r)
	{
		tree[id] = {0, {a[l], a[l]}};
		return;
	}
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	tree[id].second.first = max(tree[id * 2].second.first, tree[id * 2 + 1].second.first);
	tree[id].second.second = min(tree[id * 2].second.second, tree[id * 2 + 1].second.second);
	tree[id].first = max(tree[id * 2].first + tree[id * 2 + 1].first, max(tree[id * 2].second.first, tree[id * 2 + 1].second.first) - min(tree[id * 2].second.second, tree[id * 2 + 1].second.second));
}
 
void update(int id, int l, int r, int posl, int posr, int val)
{
	if(posr < l || posl > r)	return;
	if(r == l)
	{
		tree[id].second.first += val;
		tree[id].second.second += val;
		tree[id].first = 0;
		return;
	}
	int mid = (l + r) / 2;
	update(id * 2, l, mid, posl, posr, val);
	update(id * 2 + 1, mid + 1, r, posl, posr, val);
	tree[id].second.first = max(tree[id * 2].second.first, tree[id * 2 + 1].second.first);
	tree[id].second.second = min(tree[id * 2].second.second, tree[id * 2 + 1].second.second);
	tree[id].first = max(tree[id * 2].first + tree[id * 2 + 1].first, max(tree[id * 2].second.first, tree[id * 2 + 1].second.first) - min(tree[id * 2].second.second, tree[id * 2 + 1].second.second));
}
 
signed main()
{
	cin >> n >> q;
	for(int i = 1; i <= n; ++i)	cin >> a[i];
	build(1, 1, n);
	while(q--)
	{
		long long x, y, z;
		cin >> x >> y >> z;
		update(1, 1, n, x, y, z);
		cout << tree[1].first << "\n";
	}
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -