oj.uz

Submission #76342

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

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 619 ms 719196 KB Output is correct
2 Correct 604 ms 719328 KB Output is correct
3 Correct 610 ms 719432 KB Output is correct
4 Correct 607 ms 719432 KB Output is correct
5 Correct 614 ms 719432 KB Output is correct
6 Correct 658 ms 719440 KB Output is correct
7 Correct 596 ms 719496 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 719496 KB Output is correct
2 Correct 618 ms 719496 KB Output is correct
3 Correct 623 ms 719496 KB Output is correct
4 Correct 628 ms 719496 KB Output is correct
5 Correct 607 ms 719496 KB Output is correct
6 Correct 607 ms 719496 KB Output is correct
7 Correct 627 ms 719496 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 719196 KB Output is correct
2 Correct 604 ms 719328 KB Output is correct
3 Correct 610 ms 719432 KB Output is correct
4 Correct 607 ms 719432 KB Output is correct
5 Correct 614 ms 719432 KB Output is correct
6 Correct 658 ms 719440 KB Output is correct
7 Correct 596 ms 719496 KB Output is correct
8 Correct 2219 ms 723852 KB Output is correct
9 Correct 1970 ms 723880 KB Output is correct
10 Correct 1329 ms 723880 KB Output is correct
11 Correct 1173 ms 723924 KB Output is correct
12 Correct 1668 ms 723924 KB Output is correct
13 Correct 1312 ms 724004 KB Output is correct
14 Correct 1483 ms 724180 KB Output is correct
15 Correct 1206 ms 724180 KB Output is correct
16 Correct 1285 ms 724180 KB Output is correct
17 Correct 1282 ms 724180 KB Output is correct
18 Correct 1348 ms 724180 KB Output is correct
19 Correct 1409 ms 724180 KB Output is correct
20 Correct 2325 ms 724180 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 719496 KB Output is correct
2 Correct 618 ms 719496 KB Output is correct
3 Correct 623 ms 719496 KB Output is correct
4 Correct 628 ms 719496 KB Output is correct
5 Correct 607 ms 719496 KB Output is correct
6 Correct 607 ms 719496 KB Output is correct
7 Correct 627 ms 719496 KB Output is correct
8 Correct 1524 ms 724180 KB Output is correct
9 Correct 1889 ms 724180 KB Output is correct
10 Correct 1390 ms 724180 KB Output is correct
11 Correct 1348 ms 724180 KB Output is correct
12 Correct 1955 ms 724180 KB Output is correct
13 Correct 1487 ms 724180 KB Output is correct
14 Correct 2147 ms 729212 KB Output is correct
15 Correct 1371 ms 735148 KB Output is correct
16 Correct 1336 ms 741008 KB Output is correct
17 Correct 2033 ms 746868 KB Output is correct
18 Correct 3795 ms 752684 KB Output is correct
19 Correct 2316 ms 758496 KB Output is correct
20 Correct 1746 ms 764348 KB Output is correct
21 Correct 1332 ms 770060 KB Output is correct
22 Correct 3645 ms 776056 KB Output is correct
23 Correct 1978 ms 781756 KB Output is correct
24 Runtime error 2279 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.
25 Halted 0 ms 0 KB -