oj.uz

Submission #170431

# Submission time Handle Problem Language Result Execution time Memory
170431 2019-12-25T09:33:35 Z div2der Trading (IZhO13_trading) C++14
0 / 100
 547 ms 24372 KB 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define sz(s) (int)(s.size())
#define eb emplace_back
#define mkp make_pair
#define all(x) x.begin(), x.end()

const int N = 2e5 + 500;
const int NN = 4e3;

int a[N];

vector <int> v[N];

set <pair <int, int>> st;

int x[N], l[N], r[N];

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		cin >> l[i] >> r[i] >> x[i];
		v[l[i]].eb(i);
		int pos = -i;
		v[r[i] + 1].eb(pos);
	}
	/*for (int i = 1; i <= n; ++ i) {
		cerr << i << ": ";
		for (auto to : v[i])
			cerr << to << " ";
		cerr << '\n';
	}*/
	for (int i = 1; i <= n; ++ i) {
		int res = 0;
		for (auto to : v[i]) {
			int dif = x[to] - l[to];
			int pos = -to;
			int dif2 = x[pos] - l[pos];
			if (to <= 0)
				st.erase(mkp(dif2, pos));
			if (to >= 1)
				st.insert(mkp(dif, to));
		}
		if (!st.empty()) {
			res = (--st.end()) -> first + i;
		}
		cout << res << " ";
	}
}

int main () {
	solve();
	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 9 ms 5240 KB Output is correct
6 Correct 12 ms 5240 KB Output is correct
7 Correct 397 ms 13848 KB Output is correct
8 Correct 487 ms 15456 KB Output is correct
9 Correct 478 ms 16012 KB Output is correct
10 Correct 547 ms 16380 KB Output is correct
11 Correct 504 ms 17136 KB Output is correct
12 Runtime error 416 ms 24372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -