Submission #76324

# Submission time Handle Problem Language Result Execution time Memory
76324 2018-09-12T15:14:22 Z kig9981 None (KOI18_matrix) C++17
23 / 100
4000 ms 351004 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) {}
};

Seg2D tree[6000000];
vector<int> X, Y;
vector<tuple<int, int, int>> V;
int mN, cnt = 2;

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 = cnt++;
				tree[tree[b].yl].yp = b;
			}
			if (tree[p].yl == 0) {
				tree[p].yl = cnt++;
				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 = cnt++;
				tree[tree[b].yr].yp = b;
			}
			if (tree[p].yr == 0) {
				tree[p].yr = cnt++;
				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 = cnt++;
				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 = cnt++;
				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);
	mN = 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();
		set_tree(x, y, get_max(1, x - 1, 1, y - 1) + 1);
		if (cnt >= 6000000) for (;;);
	}
	cout << tree[1].v << '\n';
	return 0;
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:162:21: warning: unused variable 't' [-Wunused-variable]
  for (auto &[t, x, y] : V) {
                     ^
# Verdict Execution time Memory Grader output
1 Correct 213 ms 165240 KB Output is correct
2 Correct 191 ms 165460 KB Output is correct
3 Correct 200 ms 165732 KB Output is correct
4 Correct 191 ms 165956 KB Output is correct
5 Correct 202 ms 166228 KB Output is correct
6 Correct 190 ms 166396 KB Output is correct
7 Correct 189 ms 166720 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 213 ms 167056 KB Output is correct
2 Correct 191 ms 167332 KB Output is correct
3 Correct 215 ms 167604 KB Output is correct
4 Correct 251 ms 167896 KB Output is correct
5 Correct 203 ms 168204 KB Output is correct
6 Correct 198 ms 168624 KB Output is correct
7 Correct 254 ms 168920 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 213 ms 165240 KB Output is correct
2 Correct 191 ms 165460 KB Output is correct
3 Correct 200 ms 165732 KB Output is correct
4 Correct 191 ms 165956 KB Output is correct
5 Correct 202 ms 166228 KB Output is correct
6 Correct 190 ms 166396 KB Output is correct
7 Correct 189 ms 166720 KB Output is correct
8 Execution timed out 4027 ms 177164 KB Time limit exceeded
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 213 ms 167056 KB Output is correct
2 Correct 191 ms 167332 KB Output is correct
3 Correct 215 ms 167604 KB Output is correct
4 Correct 251 ms 167896 KB Output is correct
5 Correct 203 ms 168204 KB Output is correct
6 Correct 198 ms 168624 KB Output is correct
7 Correct 254 ms 168920 KB Output is correct
8 Runtime error 1071 ms 351004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -