oj.uz

Submission #41321

# Submission time Handle Problem Language Result Execution time Memory
41321 2018-02-16T00:20:58 Z MatheusLealV Trading (IZhO13_trading) C++14
100 / 100
 446 ms 13744 KB 
#include <bits/stdc++.h>
#define inf 2000000000
#define N 300005
#define l (2*nod)
#define r (2*nod + 1)
#define mid ((a + b)/2)
using namespace std;
 
int n, m, tree[4*N], lazy[4*N];
 
inline void prop(int nod, int a, int b)
{
	if(lazy[nod] == -inf) return;
 
	tree[nod] = max(tree[nod], lazy[nod]);
 
	if(a != b)
	{
		lazy[l] = max(lazy[l], lazy[nod]);
 
		lazy[r] = max(lazy[r], lazy[nod]);
	}
 
	lazy[nod] = -inf;
}
 
void build(int nod, int a, int b)
{
	if(a == b) tree[nod] = -inf;
 
	else
	{
		build(l, a, mid), build(r, mid + 1, b);
 
		tree[nod] = -inf;
	}
}
 
void upd(int nod, int a, int b, int i, int j, int x)
{
	prop(nod, a, b);
 
	if(j < a || i > b) return;
 
	if(i <= a && j >= b)
	{
		tree[nod] = max(tree[nod], x);
 
		if(a != b)
		{
			lazy[l] = max(lazy[l], x);
 
			lazy[r] = max(lazy[r], x);
		}
 
		return;
	}
 
	upd(l, a, mid, i, j, x), upd(r, mid + 1, b, i, j, x);
 
	tree[nod] = max(tree[l], tree[r]);
}
 
int query(int nod, int a, int b, int i, int j)
{
	prop(nod, a, b);
 
	if(j < a || i > b) return -inf;
 
	if(i <= a && j >= b) return tree[nod];
 
	return max(query(l, a, mid, i, j), query(r, mid + 1, b, i, j));
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n>>m;
 
	build(1, 1, n);

	for(int i = 0; i < 4*N; i++) lazy[i] = -inf;
 
	for(int i = 1, a, b, x; i <= m; i++)
	{
		cin>>a>>b>>x;
 
		upd(1, 1, n, a, b, x - a);
	}
 
	for(int i = 1; i <= n; i++)
	{
		int ans = query(1, 1, n, i, i) + i;
 
		cout<<max(0, ans)<<" \n"[i == n];
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 5 ms 5088 KB Output is correct
3 Correct 5 ms 5088 KB Output is correct
4 Correct 6 ms 5272 KB Output is correct
5 Correct 7 ms 5272 KB Output is correct
6 Correct 7 ms 5388 KB Output is correct
7 Correct 189 ms 10752 KB Output is correct
8 Correct 217 ms 11124 KB Output is correct
9 Correct 226 ms 11124 KB Output is correct
10 Correct 244 ms 11124 KB Output is correct
11 Correct 268 ms 11560 KB Output is correct
12 Correct 274 ms 11560 KB Output is correct
13 Correct 290 ms 11560 KB Output is correct
14 Correct 283 ms 11560 KB Output is correct
15 Correct 316 ms 11560 KB Output is correct
16 Correct 330 ms 11560 KB Output is correct
17 Correct 310 ms 13488 KB Output is correct
18 Correct 360 ms 13744 KB Output is correct
19 Correct 374 ms 13744 KB Output is correct
20 Correct 446 ms 13744 KB Output is correct