oj.uz

답안 #76323

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
76323 2018-09-12T15:12:07 Z kig9981 조화행렬 (KOI18_matrix) C++17
23 / 100
 2820 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 Seg2D
{
	int xp, yp, xl, xr, yl, yr, v;
	Seg2D() : xp(0), yp(0), xl(0), xr(0), yl(0), yr(0), v(0) {}
};

vector<Seg2D> tree(2);
vector<int> X, Y;
vector<tuple<int, int, int>> V;
int mN;

void CreateNode(int n, int b, int p, int s, int e)
{
	while (s < e) {
		int m = (s + e) >> 1;
		if (n <= m) {
			if (tree[b].yl == 0) {
				tree[b].yl = tree.size();
				tree.push_back(Seg2D());
				tree[tree[b].yl].yp = b;
			}
			if (tree[p].yl == 0) {
				tree[p].yl = tree.size();
				tree.push_back(Seg2D());
				tree[tree[p].yl].yp = p;
			}
			if (tree[b].xl == p) {
				tree[tree[b].yl].xl = tree[p].yl;
			}
			else {
				tree[tree[b].yl].xr = tree[p].yl;
			}
			tree[tree[p].yl].xp = tree[b].yl;
			b = tree[b].yl;
			p = tree[p].yl;
			e = m;
		}
		else {
			if (tree[b].yr == 0) {
				tree[b].yr = tree.size();
				tree.push_back(Seg2D());
				tree[tree[b].yr].yp = b;
			}
			if (tree[p].yr == 0) {
				tree[p].yr = tree.size();
				tree.push_back(Seg2D());
				tree[tree[p].yr].yp = p;
			}
			if (tree[b].xl == p) {
				tree[tree[b].yr].xl = tree[p].yr;
			}
			else {
				tree[tree[b].yr].xr = tree[p].yr;
			}
			tree[tree[p].yr].xp = tree[b].yr;
			b = tree[b].yr;
			p = tree[p].yr;
			s = m + 1;
		}
	}
}

void set_tree(int n1, int n2, int v, int p = 1, int s1 = 1, int e1 = mN, int s2 = 1, int e2 = mN)
{
	while (s1 < e1) {
		int m1 = (s1 + e1) >> 1;
		if (n1 <= m1) {
			if (tree[p].xl == 0) {
				tree[p].xl = tree.size();
				tree.push_back(Seg2D());
				tree[tree[p].xl].xp = p;
			}
			CreateNode(n2, p, tree[p].xl, s2, e2);
			p = tree[p].xl;
			e1 = m1;
		}
		else {
			if (tree[p].xr == 0) {
				tree[p].xr = tree.size();
				tree.push_back(Seg2D());
				tree[tree[p].xr].xp = p;
			}
			CreateNode(n2, p, tree[p].xr, s2, e2);
			p = tree[p].xr;
			s1 = m1 + 1;
		}
	}
	while (s2 < e2) {
		int m2 = (s2 + e2) >> 1;
		if (n2 <= m2) {
			p = tree[p].yl;
			e2 = m2;
		}
		else {
			p = tree[p].yr;
			s2 = m2 + 1;
		}
	}
	tree[p].v = v;
	for (int c = tree[p].yp; c; c = tree[c].yp) {
		tree[c].v = max(tree[tree[c].yl].v, tree[tree[c].yr].v);
	}
	for (int xc = tree[p].xp; xc; xc = tree[xc].xp) {
		tree[xc].v = max(tree[tree[xc].xl].v, tree[tree[xc].xr].v);
		for (int yc = tree[xc].yp; yc; yc = tree[yc].yp) {
			tree[yc].v = max(max(tree[tree[yc].xl].v, tree[tree[yc].xr].v), max(tree[tree[yc].yl].v, tree[tree[yc].yr].v));
		}
	}
}

int get_max(int x1, int x2, int y1, int y2, int p = 1, int s1 = 1, int e1 = mN, int s2 = 1, int e2 = mN)
{
	int m1 = (s1 + e1) >> 1, m2 = (s2 + e2) >> 1;
	if (p == 0 || x2 < x1 || x2 < s1 || e1 < x1 || y2 < y1 || y2 < s2 || e2 < y1) {
		return 0;
	}
	if (x1 <= s1 && e1 <= x2) {
		if (y1 <= s2 && e2 <= y2) {
			return tree[p].v;
		}
		return max(get_max(x1, x2, y1, y2, tree[p].yl, s1, e1, s2, m2), get_max(x1, x2, y1, y2, tree[p].yr, s1, e1, m2 + 1, e2));
	}
	return max(get_max(x1, x2, y1, y2, tree[p].xl, s1, m1, s2, e2), get_max(x1, x2, y1, y2, tree[p].xr, m1 + 1, e1, s2, e2));
}

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 M, N;
	cin >> M >> N;
	V.resize(N);
	for (mN = 1; mN < N; mN <<= 1);
	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();
		set_tree(x, y, get_max(1, x - 1, 1, y - 1) + 1);
	}
	cout << tree[1].v << '\n';
	return 0;
}

Compilation message

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

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 58588 KB Output is correct
2 Correct 104 ms 58588 KB Output is correct
3 Correct 113 ms 58588 KB Output is correct
4 Correct 95 ms 58588 KB Output is correct
5 Correct 150 ms 59472 KB Output is correct
6 Correct 89 ms 59472 KB Output is correct
7 Correct 93 ms 59472 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 59472 KB Output is correct
2 Correct 99 ms 59472 KB Output is correct
3 Correct 139 ms 59472 KB Output is correct
4 Correct 196 ms 61292 KB Output is correct
5 Correct 108 ms 61292 KB Output is correct
6 Correct 91 ms 61292 KB Output is correct
7 Correct 179 ms 62140 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 58588 KB Output is correct
2 Correct 104 ms 58588 KB Output is correct
3 Correct 113 ms 58588 KB Output is correct
4 Correct 95 ms 58588 KB Output is correct
5 Correct 150 ms 59472 KB Output is correct
6 Correct 89 ms 59472 KB Output is correct
7 Correct 93 ms 59472 KB Output is correct
8 Runtime error 2527 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

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 59472 KB Output is correct
2 Correct 99 ms 59472 KB Output is correct
3 Correct 139 ms 59472 KB Output is correct
4 Correct 196 ms 61292 KB Output is correct
5 Correct 108 ms 61292 KB Output is correct
6 Correct 91 ms 61292 KB Output is correct
7 Correct 179 ms 62140 KB Output is correct
8 Runtime error 2820 ms 787456 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -