oj.uz

Submission #76341

# Submission time Handle Problem Language Result Execution time Memory
76341 2018-09-12T19:21:20 Z kig9981 None (KOI18_matrix) C++17
38 / 100
 2294 ms 786548 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, cnt = 1 << 19;
vector<int> X, Y;
vector<tuple<int, int, int>> V;
SegTree tree[64000000];

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 = cnt++;
		}
		add_tree2(y, v, tree[bit].l, s, m);
	}
	else {
		if (tree[bit].r == 0) {
			tree[bit].r = cnt++;
		}
		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:116:21: warning: unused variable 't' [-Wunused-variable]
  for (auto &[t, x, y] : V) {
                     ^
matrix.cpp:91:6: warning: unused variable 'mN' [-Wunused-variable]
  int mN;
      ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 752248 KB Output is correct
2 Correct 648 ms 752616 KB Output is correct
3 Correct 638 ms 752616 KB Output is correct
4 Correct 631 ms 752616 KB Output is correct
5 Correct 629 ms 752684 KB Output is correct
6 Correct 659 ms 752684 KB Output is correct
7 Correct 627 ms 752684 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 752684 KB Output is correct
2 Correct 636 ms 752692 KB Output is correct
3 Correct 654 ms 752708 KB Output is correct
4 Correct 671 ms 752728 KB Output is correct
5 Correct 624 ms 752728 KB Output is correct
6 Correct 641 ms 752824 KB Output is correct
7 Correct 675 ms 752824 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 752248 KB Output is correct
2 Correct 648 ms 752616 KB Output is correct
3 Correct 638 ms 752616 KB Output is correct
4 Correct 631 ms 752616 KB Output is correct
5 Correct 629 ms 752684 KB Output is correct
6 Correct 659 ms 752684 KB Output is correct
7 Correct 627 ms 752684 KB Output is correct
8 Correct 2294 ms 757168 KB Output is correct
9 Correct 2064 ms 758048 KB Output is correct
10 Correct 1370 ms 758096 KB Output is correct
11 Correct 1214 ms 758144 KB Output is correct
12 Correct 1711 ms 758144 KB Output is correct
13 Correct 1335 ms 758144 KB Output is correct
14 Correct 1537 ms 758144 KB Output is correct
15 Correct 1240 ms 758144 KB Output is correct
16 Correct 1315 ms 758160 KB Output is correct
17 Correct 1317 ms 758160 KB Output is correct
18 Correct 1346 ms 758160 KB Output is correct
19 Correct 1391 ms 758160 KB Output is correct
20 Correct 2250 ms 758160 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 752684 KB Output is correct
2 Correct 636 ms 752692 KB Output is correct
3 Correct 654 ms 752708 KB Output is correct
4 Correct 671 ms 752728 KB Output is correct
5 Correct 624 ms 752728 KB Output is correct
6 Correct 641 ms 752824 KB Output is correct
7 Correct 675 ms 752824 KB Output is correct
8 Correct 1592 ms 758160 KB Output is correct
9 Correct 2138 ms 763384 KB Output is correct
10 Correct 1442 ms 769240 KB Output is correct
11 Correct 1335 ms 775176 KB Output is correct
12 Correct 1990 ms 781020 KB Output is correct
13 Runtime error 1446 ms 786548 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.
14 Halted 0 ms 0 KB -