oj.uz

Submission #76343

# Submission time Handle Problem Language Result Execution time Memory
76343 2018-09-12T19:24:58 Z kig9981 None (KOI18_matrix) C++17
100 / 100
 3872 ms 704080 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[55555555];

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 592 ms 653048 KB Output is correct
2 Correct 577 ms 653180 KB Output is correct
3 Correct 561 ms 653180 KB Output is correct
4 Correct 543 ms 653180 KB Output is correct
5 Correct 550 ms 653180 KB Output is correct
6 Correct 546 ms 653180 KB Output is correct
7 Correct 547 ms 653296 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 653296 KB Output is correct
2 Correct 582 ms 653296 KB Output is correct
3 Correct 579 ms 653296 KB Output is correct
4 Correct 583 ms 653296 KB Output is correct
5 Correct 553 ms 653296 KB Output is correct
6 Correct 548 ms 653296 KB Output is correct
7 Correct 568 ms 653296 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 653048 KB Output is correct
2 Correct 577 ms 653180 KB Output is correct
3 Correct 561 ms 653180 KB Output is correct
4 Correct 543 ms 653180 KB Output is correct
5 Correct 550 ms 653180 KB Output is correct
6 Correct 546 ms 653180 KB Output is correct
7 Correct 547 ms 653296 KB Output is correct
8 Correct 2165 ms 657688 KB Output is correct
9 Correct 1955 ms 657720 KB Output is correct
10 Correct 1295 ms 657780 KB Output is correct
11 Correct 1117 ms 657780 KB Output is correct
12 Correct 1635 ms 657780 KB Output is correct
13 Correct 1243 ms 657780 KB Output is correct
14 Correct 1464 ms 657780 KB Output is correct
15 Correct 1166 ms 657780 KB Output is correct
16 Correct 1224 ms 657780 KB Output is correct
17 Correct 1242 ms 657780 KB Output is correct
18 Correct 1292 ms 657780 KB Output is correct
19 Correct 1315 ms 657780 KB Output is correct
20 Correct 2140 ms 657808 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 653296 KB Output is correct
2 Correct 582 ms 653296 KB Output is correct
3 Correct 579 ms 653296 KB Output is correct
4 Correct 583 ms 653296 KB Output is correct
5 Correct 553 ms 653296 KB Output is correct
6 Correct 548 ms 653296 KB Output is correct
7 Correct 568 ms 653296 KB Output is correct
8 Correct 1465 ms 657808 KB Output is correct
9 Correct 1978 ms 657808 KB Output is correct
10 Correct 1327 ms 657808 KB Output is correct
11 Correct 1317 ms 657808 KB Output is correct
12 Correct 1836 ms 657808 KB Output is correct
13 Correct 1362 ms 657808 KB Output is correct
14 Correct 2091 ms 657808 KB Output is correct
15 Correct 1271 ms 658004 KB Output is correct
16 Correct 1302 ms 658004 KB Output is correct
17 Correct 1956 ms 658004 KB Output is correct
18 Correct 3872 ms 658004 KB Output is correct
19 Correct 2190 ms 658004 KB Output is correct
20 Correct 1688 ms 658004 KB Output is correct
21 Correct 1291 ms 658004 KB Output is correct
22 Correct 3619 ms 658004 KB Output is correct
23 Correct 1956 ms 658004 KB Output is correct
24 Correct 2256 ms 658004 KB Output is correct
25 Correct 2722 ms 663296 KB Output is correct
26 Correct 2614 ms 669124 KB Output is correct
27 Correct 1858 ms 675032 KB Output is correct
28 Correct 1314 ms 680736 KB Output is correct
29 Correct 1987 ms 686584 KB Output is correct
30 Correct 1879 ms 692376 KB Output is correct
31 Correct 2663 ms 698136 KB Output is correct
32 Correct 1936 ms 704080 KB Output is correct