1801C - Music Festival - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int 
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define fr first
#define sc second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

#define lowbit(x)    ((x) & -(x))
#define all(x)       (x).begin(), (x).end()
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

inline T rd() {
    T x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 200007

#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)

int c[262145 << 2];

void build(int rt, int l, int r) {
	c[rt] = 0;
	if (l == r) return;
	build(ls, l, mid);
	build(rs, mid + 1, r);
}

void upd(int rt, int l, int r, int p, int x) {
	if (l == r) {c[rt] = max(c[rt], x); return;}
	p <= mid ? upd(ls, l, mid, p, x) : upd(rs, mid + 1, r, p, x);
	c[rt] = max(c[ls], c[rs]);
}

int query(int rt, int l, int r, int L, int R) {
	if (L <= l && r <= R) return c[rt];
	int ans = 0;
	if (L <= mid) ans = max(ans, query(ls, l, mid, L, R));
	if (R > mid) ans = max(ans, query(rs, mid + 1, r, L, R));
	return ans;
}

int a[N], b[N], e[N];

vector<int> s;

vector<pii> t;

inline void work() {
	int n = rd();
	s.clear(); t.clear();
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		int k = rd(), mx = 0;
		b[i] = cnt + 1;
		for (int j = 1; j <= k; ++j) {
			int x = rd(); 
			if (x <= mx) continue;
			s.pb(a[++cnt] = x); mx = x;
		}
		e[i] = cnt;
		t.eb(mx, i);
	}
	
	sort(all(t));
	sort(all(s));
	s.erase(unique(all(s)), s.end());
	for (int i = 1; i <= cnt; ++i) 
		a[i] = lower_bound(all(s), a[i]) - s.begin() + 1;
	
	int m = s.size();
	build(1, 1, m); 
	for (auto [mx, i] : t) {
		int tmp = e[i] - b[i] + 1;
		for (int j = b[i]; j <= e[i]; ++j) 
			if (a[j] > 1) tmp = max(tmp, query(1, 1, m, 1, a[j] - 1) + e[i] - j + 1);
		upd(1, 1, m, a[e[i]], tmp);
	}
	printf("%d\n", query(1, 1, m, 1, m));
}

int main() {
	for (int t = rd(); t; --t) work();
    return 0;
}