oj.uz

Submission #76340

# Submission time Handle Problem Language Result Execution time Memory
76340 2018-09-12T19:19:28 Z kig9981 None (KOI18_matrix) C++17
23 / 100
 2689 ms 787456 KB 
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

struct SegTree
{
	int l, r, v;
	SegTree() : l(0), r(0), v(0) {}
};

int M, N;
vector<int> X, Y;
vector<tuple<int, int, int>> V;
vector<SegTree> tree(1 << 19);

void add_tree2(int y, int v, int bit, int s = 1, int e = N)
{
	int m = (s + e) >> 1;
	if (s == e) {
		tree[bit].v = v;
		return;
	}
	if (y <= m) {
		if (tree[bit].l == 0) {
			tree[bit].l = tree.size();
			tree.push_back(SegTree());
		}
		add_tree2(y, v, tree[bit].l, s, m);
	}
	else {
		if (tree[bit].r == 0) {
			tree[bit].r = tree.size();
			tree.push_back(SegTree());
		}
		add_tree2(y, v, tree[bit].r, m + 1, e);
	}
	tree[bit].v = max(tree[tree[bit].l].v, tree[tree[bit].r].v);
}

void add_tree(int x, int y, int v, int bit = 1, int s = 1, int e = N)
{
	while (s < e) {
		int m = (s + e) >> 1;
		add_tree2(y, v, bit);
		if (x <= m) {
			bit = bit << 1;
			e = m;
		}
		else {
			bit = (bit << 1) + 1;
			s = m + 1;
		}
	}
	add_tree2(y, v, bit);
}

int get_max2(int n1, int n2, int bit, int s = 1, int e = N)
{
	int m = (s + e) >> 1;
	if (bit==0 || n2 < n1 || n2 < s || e < n1) {
		return 0;
	}
	if (n1 <= s && e <= n2) {
		return tree[bit].v;
	}
	return max(get_max2(n1, n2, tree[bit].l, s, m), get_max2(n1, n2, tree[bit].r, m + 1, e));
}

int get_max(int n2, int y, int n1 = 1, int bit = 1, int s = 1, int e = N)
{
	int m = (s + e) >> 1;
	if (n2 < n1 || n2 < s || e < n1) {
		return 0;
	}
	if (n1 <= s && e <= n2) {
		return get_max2(1,y,bit);
	}
	return max(get_max(n2, y, n1, 2 * bit, s, m), get_max(n2, y, n1, 2 * bit + 1, m + 1, e));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	int mN;
	cin >> M >> N;
	V.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> get<0>(V[i]);
	}
	for (int i = 0; i < N; i++) {
		cin >> get<1>(V[i]);
		X.push_back(get<1>(V[i]));
	}
	sort(X.begin(), X.end());
	if (M == 3) {
		for (int i = 0; i < N; i++) {
			cin >> get<2>(V[i]);
			Y.push_back(get<2>(V[i]));
		}
		sort(V.begin(), V.end());
		sort(Y.begin(), Y.end());
	}
	else {
		sort(V.begin(), V.end());
		for (int i = 0; i < N; i++) {
			Y.push_back(get<2>(V[i]) = i);
		}
	}
	for (auto &[t, x, y] : V) {
		x = upper_bound(X.begin(), X.end(), x) - X.begin();
		y = upper_bound(Y.begin(), Y.end(), y) - Y.begin();
		add_tree(x, y, get_max(x, y) + 1);
	}
	cout << tree[1].v << '\n';
	return 0;
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:118:21: warning: unused variable 't' [-Wunused-variable]
  for (auto &[t, x, y] : V) {
                     ^
matrix.cpp:93:6: warning: unused variable 'mN' [-Wunused-variable]
  int mN;
      ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 25192 KB Output is correct
2 Correct 71 ms 25444 KB Output is correct
3 Correct 72 ms 25444 KB Output is correct
4 Correct 61 ms 25444 KB Output is correct
5 Correct 76 ms 25444 KB Output is correct
6 Correct 47 ms 25444 KB Output is correct
7 Correct 58 ms 25444 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 25444 KB Output is correct
2 Correct 63 ms 25444 KB Output is correct
3 Correct 79 ms 25444 KB Output is correct
4 Correct 85 ms 25460 KB Output is correct
5 Correct 69 ms 25484 KB Output is correct
6 Correct 48 ms 25484 KB Output is correct
7 Correct 95 ms 25552 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 25192 KB Output is correct
2 Correct 71 ms 25444 KB Output is correct
3 Correct 72 ms 25444 KB Output is correct
4 Correct 61 ms 25444 KB Output is correct
5 Correct 76 ms 25444 KB Output is correct
6 Correct 47 ms 25444 KB Output is correct
7 Correct 58 ms 25444 KB Output is correct
8 Runtime error 2689 ms 787456 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 25444 KB Output is correct
2 Correct 63 ms 25444 KB Output is correct
3 Correct 79 ms 25444 KB Output is correct
4 Correct 85 ms 25460 KB Output is correct
5 Correct 69 ms 25484 KB Output is correct
6 Correct 48 ms 25484 KB Output is correct
7 Correct 95 ms 25552 KB Output is correct
8 Runtime error 1713 ms 787456 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
9 Halted 0 ms 0 KB -