Submission #76342

#	Time	Username	Problem	Language	Result	Execution time	Memory
76342		kig9981	조화행렬 (KOI18_matrix)	C++17	38 / 100	3795 ms	787456 KiB

matrix

#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 (stderr)

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 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 0 / 62