oj.uz

Submission #76335

# Submission time Handle Problem Language Result Execution time Memory
76335 2018-09-12T18:03:45 Z kig9981 None (KOI18_matrix) C++17
29 / 100
 1125 ms 255640 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 38136 KB Output is correct
2 Correct 68 ms 38256 KB Output is correct
3 Correct 69 ms 38292 KB Output is correct
4 Correct 68 ms 38292 KB Output is correct
5 Correct 68 ms 38292 KB Output is correct
6 Correct 66 ms 38292 KB Output is correct
7 Correct 66 ms 38292 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 38292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 38136 KB Output is correct
2 Correct 68 ms 38256 KB Output is correct
3 Correct 69 ms 38292 KB Output is correct
4 Correct 68 ms 38292 KB Output is correct
5 Correct 68 ms 38292 KB Output is correct
6 Correct 66 ms 38292 KB Output is correct
7 Correct 66 ms 38292 KB Output is correct
8 Correct 1062 ms 208816 KB Output is correct
9 Correct 925 ms 212836 KB Output is correct
10 Correct 636 ms 216696 KB Output is correct
11 Correct 595 ms 220532 KB Output is correct
12 Correct 792 ms 224396 KB Output is correct
13 Correct 595 ms 228528 KB Output is correct
14 Correct 710 ms 232224 KB Output is correct
15 Correct 588 ms 236140 KB Output is correct
16 Correct 592 ms 240020 KB Output is correct
17 Correct 616 ms 243772 KB Output is correct
18 Correct 596 ms 247788 KB Output is correct
19 Correct 633 ms 251652 KB Output is correct
20 Correct 1125 ms 255640 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 38292 KB Output isn't correct
2 Halted 0 ms 0 KB -