oj.uz

Submission #538890

# Submission time Handle Problem Language Result Execution time Memory
538890 2022-03-18T01:08:53 Z GioChkhaidze Trading (IZhO13_trading) C++14
100 / 100
 177 ms 12620 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int n, m, L, R, X, inf = 1e9;
vector < int > v(4 * N, -inf);

void upd(int h, int l, int r) {
	if (r < L || R < l) return ;
	if (L <= l && r <= R) {
		v[h] = max(v[h], X - L);
		return ;
	}
	upd((h << 1), l, ((l + r) >> 1));
	upd(((h << 1) | 1), ((l + r) >> 1) + 1, r);
}

void dfs(int h, int l, int r, int mx) {
	if (l == r) {
		if (mx == -inf) 
			cout << 0 << " ";
				else 
			cout << l + mx << " ";		
		return ;
	}
	dfs((h << 1), l, ((l + r) >> 1), max(mx, v[(h << 1)]));
	dfs(((h << 1) | 1), ((l + r) >> 1) + 1, r, max(mx, v[((h << 1) | 1)]));
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> L >> R >> X;
		upd(1, 1, n);
	}
	dfs(1, 1, n, v[1]);
}

Compilation message

trading.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main () {
      | ^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4928 KB Output is correct
6 Correct 6 ms 5036 KB Output is correct
7 Correct 87 ms 8676 KB Output is correct
8 Correct 102 ms 9292 KB Output is correct
9 Correct 110 ms 9252 KB Output is correct
10 Correct 111 ms 9292 KB Output is correct
11 Correct 116 ms 10116 KB Output is correct
12 Correct 122 ms 10192 KB Output is correct
13 Correct 135 ms 10504 KB Output is correct
14 Correct 131 ms 10380 KB Output is correct
15 Correct 145 ms 11156 KB Output is correct
16 Correct 161 ms 11200 KB Output is correct
17 Correct 172 ms 11280 KB Output is correct
18 Correct 169 ms 11724 KB Output is correct
19 Correct 171 ms 11468 KB Output is correct
20 Correct 177 ms 12620 KB Output is correct