Submission #76335

#	Time	Username	Problem	Language	Result	Execution time	Memory
76335		kig9981	조화행렬 (KOI18_matrix)	C++17	29 / 100	1125 ms	255640 KiB

matrix

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

struct SplayTree
{
	SplayTree *p, *l, *r;
	int v, max, cv;
	SplayTree() : v(0), max(0), cv(0), p(NULL), l(NULL), r(NULL) {}
};

vector<int> X, Y;
vector<tuple<int, int, int>> V;
SplayTree *tree[1 << 19];

void update(SplayTree *&c)
{
	c->max = c->cv;
	if (c->l) c->max = max(c->max, c->l->max);
	if (c->r) c->max = max(c->max, c->r->max);
}

void rotate(SplayTree *c)
{
	SplayTree *p = c->p, *b;
	if (p->l == c) {
		p->l = b = c->r;
		c->r = p;
	}
	else {
		p->r = b = c->l;
		c->l = p;
	}
	c->p = p->p;
	p->p = c;
	if (b) b->p = p;
	if (c->p) {
		if (c->p->l == p) c->p->l = c;
		else c->p->r = c;
	}
	update(p);
	update(c);
}

void Splay(SplayTree *c)
{
	if (c->p == NULL) return;
	while (c->p) {
		if (c->p->p == NULL) {
			rotate(c);
		}
		else if (c == c->p->l && c->p == c->p->p->l || c == c->p->r && c->p == c->p->p->r) {
			rotate(c->p);
			rotate(c);
		}
		else {
			rotate(c);
			rotate(c);
		}
	}
}

SplayTree *insert(SplayTree *c, int key, int v)
{
	for (;;) {
		if (c->v < key) {
			if (c->r == NULL) {
				c->r = new SplayTree;
				c->r->v = key;
				c->r->cv = v;
				c->r->p = c;
				Splay(c = c->r);
				break;
			}
			else {
				c = c->r;
			}
		}
		else if (c->v > key) {
			if (c->l == NULL) {
				c->l = new SplayTree;
				c->l->v = key;
				c->l->cv = v;
				c->l->p = c;
				Splay(c = c->l);
				break;
			}
			else {
				c = c->l;
			}
		}
	}
	return c;
}

SplayTree *upper_bound(SplayTree *c, int key)
{
	while (c->v <= key || c->l && c->l->v > key) {
		if (c->v <= key) {
			c = c->r;
		}
		else if (c->l && c->l->v > key) {
			c = c->l;
		}
	}
	Splay(c);
	return c;
}

void add_tree(int x, int y, int v, int bit = 1, int s = 1, int e = 200000)
{
	while (s < e) {
		int m = (s + e) >> 1;
		tree[bit] = insert(tree[bit], y, v);
		if (x <= m) {
			bit = bit << 1;
			e = m;
		}
		else {
			bit = (bit << 1) + 1;
			s = m + 1;
		}
	}
	tree[bit] = insert(tree[bit], y, v);
}

int get_max(int n2, int y, int n1 = 1, int bit = 1, int s = 1, int e = 200000)
{
	int m = (s + e) >> 1;
	if (n2 < n1 || n2 < s || e < n1) {
		return 0;
	}
	if (n1 <= s && e <= n2) {
		tree[bit] = upper_bound(tree[bit], y);
		return tree[bit]->l ? tree[bit]->l->max : 0;
	}
	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 M, N;
	for (int i = 1; i < (1 << 19); i++) {
		tree[i] = new SplayTree;
		tree[i]->v = 0x7fffffff;
	}
	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 - 1, y - 1) + 1);
	}
	cout << tree[1]->max << '\n';
	return 0;
}

Compilation message (stderr)

matrix.cpp: In constructor 'SplayTree::SplayTree()':
matrix.cpp:14:14: warning: 'SplayTree::cv' will be initialized after [-Wreorder]
  int v, max, cv;
              ^~
matrix.cpp:13:13: warning:   'SplayTree* SplayTree::p' [-Wreorder]
  SplayTree *p, *l, *r;
             ^
matrix.cpp:15:2: warning:   when initialized here [-Wreorder]
  SplayTree() : v(0), max(0), cv(0), p(NULL), l(NULL), r(NULL) {}
  ^~~~~~~~~
matrix.cpp: In function 'void Splay(SplayTree*)':
matrix.cpp:58:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   else if (c == c->p->l && c->p == c->p->p->l || c == c->p->r && c->p == c->p->p->r) {
            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
matrix.cpp: In function 'SplayTree* upper_bound(SplayTree*, int)':
matrix.cpp:104:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  while (c->v <= key || c->l && c->l->v > key) {
                        ~~~~~^~~~~~~~~~~~~~~~
matrix.cpp: In function 'int main()':
matrix.cpp:181:21: warning: unused variable 't' [-Wunused-variable]
  for (auto &[t, x, y] : V) {
                     ^

• Subtask 1: 14 / 14
• Subtask 2: 0 / 9
• Subtask 3: 15 / 15
• Subtask 4: 0 / 62