Submission #249739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249739	2020-07-15T16:25:17 Z	srvlt	Trading (IZhO13_trading)	C++14	100 / 100	309 ms	28384 KB

trading

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 3e5 + 123;
int n, m;
vector <array <int, 2> > q[n0];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		q[l].pb({0, x - l}), q[r + 1].pb({1, x - l});
	}
	multiset <int> st;
	for (int i = 1; i <= n; i++) {
		sort(all(q[i]));
		for (auto j : q[i]) {
			if (j[0] == 0) st.insert(j[1]);
			else st.erase(st.find(j[1]));
		}
		if (st.empty()) cout << 0 << ' ';
		else cout << *(--st.end()) + i << ' ';
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7424 KB	Output is correct
2	Correct	5 ms	7424 KB	Output is correct
3	Correct	5 ms	7424 KB	Output is correct
4	Correct	5 ms	7424 KB	Output is correct
5	Correct	7 ms	7552 KB	Output is correct
6	Correct	7 ms	7552 KB	Output is correct
7	Correct	149 ms	17892 KB	Output is correct
8	Correct	167 ms	19608 KB	Output is correct
9	Correct	179 ms	20392 KB	Output is correct
10	Correct	191 ms	21600 KB	Output is correct
11	Correct	191 ms	21764 KB	Output is correct
12	Correct	222 ms	24032 KB	Output is correct
13	Correct	230 ms	22484 KB	Output is correct
14	Correct	230 ms	23008 KB	Output is correct
15	Correct	273 ms	24936 KB	Output is correct
16	Correct	294 ms	24296 KB	Output is correct
17	Correct	269 ms	24676 KB	Output is correct
18	Correct	265 ms	28384 KB	Output is correct
19	Correct	274 ms	25184 KB	Output is correct
20	Correct	309 ms	27876 KB	Output is correct