Submission #2049638

---

Source Code Expand

#include <bits/stdc++.h>
#include <random>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<ll, ll> ll_ll;
struct edge { int v, w; };
const int INF = INT_MAX / 2;;
const int MOD = 1e9 + 7;
const int e9 = 1e9;
const ll e18 = 1e18;

template <class Monoid>
struct segtree {
	using T = typename Monoid::T;
	int N;
	vector<T> a;
	segtree(const vector<T> &a0) {
		for (N = 1; N < a0.size(); N<<=1);
		a.resize(N<<1);
		copy(a0.begin(), a0.end(), a.begin() + N);
		for (int i = N - 1; i; i--)
			a[i] = Monoid::op(a[i<<1], a[i<<1 | 1]);
	}
	segtree(int N, const T &x = Monoid::id()) :
		segtree(vector<T>(N, x)) {}
	T get(int l, int r) {
		T xl = Monoid::id(), xr = Monoid::id();
		for (l += N, r += N; l < r; l>>=1, r>>=1) {
			if (l & 1) xl = Monoid::op(xl, a[l++]);
			if (r & 1) xr = Monoid::op(a[--r], xr);
		}
		return Monoid::op(xl, xr);
	}
	void set(int i, const T &x) {
		i += N;
		a[i] = max(a[i], x);
		while (i>>=1) a[i] = Monoid::op(a[i<<1], a[i<<1 | 1]);
	}
};

struct monoid {
	using T = int;
	static T id() { return 0; }
	static T op(const T &l, const T &r) {
		return max(l, r);
	}
};

int main() {
	int N, K; cin >> N >> K; K++;
	vector<int> a(N);
	rep(i, N) scanf("%d", &a[i]);
	vector<int> A = a;
	sort(A.begin(), A.end());
	A.erase(unique(A.begin(), A.end()), A.end());
	int M = A.size();
	rep(i, N) a[i] = lower_bound(A.begin(), A.end(), a[i]) - A.begin();
	vector<segtree<monoid>> st(K, segtree<monoid>(M));
	rep(i, N) rep(k, K) {
		int x = st[k].get(0, a[i]);
		if (k) x = max(x, st[k - 1].get(0, M));
		st[k].set(a[i], x + 1);
	}
	int ans = 0;
	rep(k, K) ans = max(ans, st[k].get(0, M));
	cout << ans << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i, N) scanf("%d", &a[i]);
                              ^

Judge Result