oj.uz

Submission #639884

# Submission time Handle Problem Language Result Execution time Memory
639884 2022-09-12T15:44:40 Z starchan Trading (IZhO13_trading) C++17
100 / 100
 345 ms 26772 KB 
#include<bits/stdc++.h>
using namespace std;
#define double long double
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+1
#define LMX (int)12e5+50
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
struct segment_tree
{
	vector<int> tree;
	vector<int> lazy;
	void init()
	{
		tree.assign(LMX, -INF);
		lazy.assign(LMX, -INF);
		return;
	}
	void push(int id)
	{
		tree[2*id] = max(tree[2*id], lazy[id]);
		tree[2*id+1] = max(tree[2*id+1], lazy[id]);
		lazy[2*id] = max(lazy[2*id], lazy[id]);
		lazy[2*id+1] = max(lazy[2*id+1], lazy[id]);
		lazy[id] = -INF;
		return;
	}
	void maximise(int val, int ql, int qr, int id, int l, int r)
	{
		if(r < ql || qr < l)
			return;
		if(ql <= l && r <= qr)
		{
			tree[id] = max(tree[id], val);
			lazy[id] = max(lazy[id], val);
			return;
		}
		int m = (l+r)/2;
		push(id);
		maximise(val, ql, qr, 2*id, l, m);
		maximise(val, ql, qr, 2*id+1, m+1, r);
		tree[id] = max(tree[2*id], tree[2*id+1]);
		return;
	}
	int point(int x, int id, int l, int r)
	{
		if(l==r)
			return tree[id];
		push(id);
		int m = (l+r)/2;
		if(x <= m)
			return point(x, 2*id, l, m);
		else
			return point(x, 2*id+1, m+1, r);
	}
};
signed main()
{
	fast();
	int n, q;
	cin >> n >> q;
	segment_tree work;
	work.init();
	while(q--)
	{
		int l, r, x;
		cin >> l >> r >> x;
		work.maximise(x-l, l, r, 1, 1, n);
	}
	for(int i = 1; i <= n; i++)
		cout << max(work.point(i, 1, 1, n)+i, 0ll) << " ";
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Correct 8 ms 19008 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 10 ms 19028 KB Output is correct
5 Correct 14 ms 19028 KB Output is correct
6 Correct 13 ms 19160 KB Output is correct
7 Correct 158 ms 22800 KB Output is correct
8 Correct 169 ms 23424 KB Output is correct
9 Correct 184 ms 23440 KB Output is correct
10 Correct 201 ms 23432 KB Output is correct
11 Correct 233 ms 24268 KB Output is correct
12 Correct 233 ms 24464 KB Output is correct
13 Correct 265 ms 24656 KB Output is correct
14 Correct 237 ms 24464 KB Output is correct
15 Correct 303 ms 25244 KB Output is correct
16 Correct 281 ms 25240 KB Output is correct
17 Correct 267 ms 25356 KB Output is correct
18 Correct 297 ms 25872 KB Output is correct
19 Correct 312 ms 25480 KB Output is correct
20 Correct 345 ms 26772 KB Output is correct