Submission #2049638


Source Code Expand

Copy
#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

Submission Time
Task B - だんだん強く
User sugim48
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1836 Byte
Status WA
Exec Time 2079 ms
Memory 105976 KB

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

Set Name All
Score / Max Score 0 / 800
Status
AC × 43
WA × 25
Set Name Test Cases
All 00_sample00, 00_sample01, 00_sample02, 01_minimal00, 01_minimal01, 01_minimal02, 01_minimal03, 20_small_random00, 20_small_random01, 20_small_random02, 20_small_random03, 20_small_random04, 20_small_random05, 20_small_random06, 20_small_random07, 20_small_random08, 20_small_random09, 20_small_random10, 20_small_random11, 20_small_random12, 20_small_random13, 20_small_random14, 20_small_random15, 20_small_random16, 20_small_random17, 20_small_random18, 20_small_random19, 21_small_increasing00, 21_small_increasing01, 21_small_increasing02, 21_small_increasing03, 21_small_increasing04, 21_small_increasing05, 22_small_decreasing00, 22_small_decreasing01, 22_small_decreasing02, 22_small_decreasing03, 22_small_decreasing04, 22_small_decreasing05, 23_small_mountain00, 23_small_mountain01, 23_small_mountain02, 23_small_mountain03, 23_small_mountain04, 23_small_mountain05, 24_small_valley00, 24_small_valley01, 24_small_valley02, 24_small_valley03, 24_small_valley04, 24_small_valley05, 30_large_random00, 30_large_random01, 30_large_random02, 30_large_random03, 30_large_random04, 31_large_increasing00, 31_large_increasing01, 31_large_increasing02, 32_large_decreasing00, 32_large_decreasing01, 32_large_decreasing02, 33_large_mountain00, 33_large_mountain01, 33_large_mountain02, 34_large_valley00, 34_large_valley01, 34_large_valley02
Case Name Status Exec Time Memory
00_sample00 AC 1 ms 256 KB
00_sample01 AC 1 ms 256 KB
00_sample02 AC 1 ms 256 KB
01_minimal00 AC 1 ms 256 KB
01_minimal01 WA 1 ms 256 KB
01_minimal02 AC 1 ms 256 KB
01_minimal03 WA 1 ms 256 KB
20_small_random00 AC 1 ms 256 KB
20_small_random01 WA 2 ms 384 KB
20_small_random02 AC 1 ms 256 KB
20_small_random03 WA 1 ms 256 KB
20_small_random04 AC 1 ms 256 KB
20_small_random05 AC 1 ms 256 KB
20_small_random06 AC 1 ms 256 KB
20_small_random07 AC 1 ms 256 KB
20_small_random08 WA 1 ms 256 KB
20_small_random09 WA 2 ms 384 KB
20_small_random10 AC 1 ms 256 KB
20_small_random11 WA 1 ms 384 KB
20_small_random12 WA 2 ms 384 KB
20_small_random13 WA 2 ms 384 KB
20_small_random14 WA 1 ms 256 KB
20_small_random15 AC 1 ms 256 KB
20_small_random16 AC 1 ms 256 KB
20_small_random17 WA 1 ms 256 KB
20_small_random18 AC 1 ms 256 KB
20_small_random19 AC 1 ms 256 KB
21_small_increasing00 AC 1 ms 256 KB
21_small_increasing01 WA 1 ms 256 KB
21_small_increasing02 WA 1 ms 256 KB
21_small_increasing03 WA 1 ms 256 KB
21_small_increasing04 WA 2 ms 384 KB
21_small_increasing05 WA 2 ms 384 KB
22_small_decreasing00 AC 1 ms 256 KB
22_small_decreasing01 AC 1 ms 256 KB
22_small_decreasing02 AC 1 ms 256 KB
22_small_decreasing03 AC 1 ms 256 KB
22_small_decreasing04 AC 2 ms 384 KB
22_small_decreasing05 WA 2 ms 384 KB
23_small_mountain00 AC 1 ms 256 KB
23_small_mountain01 AC 1 ms 256 KB
23_small_mountain02 AC 1 ms 256 KB
23_small_mountain03 WA 1 ms 256 KB
23_small_mountain04 WA 1 ms 256 KB
23_small_mountain05 WA 2 ms 256 KB
24_small_valley00 AC 1 ms 256 KB
24_small_valley01 AC 1 ms 256 KB
24_small_valley02 AC 1 ms 256 KB
24_small_valley03 WA 1 ms 256 KB
24_small_valley04 WA 1 ms 256 KB
24_small_valley05 WA 2 ms 256 KB
30_large_random00 AC 1493 ms 54520 KB
30_large_random01 AC 808 ms 34936 KB
30_large_random02 AC 43 ms 3064 KB
30_large_random03 AC 104 ms 7160 KB
30_large_random04 AC 923 ms 42100 KB
31_large_increasing00 AC 30 ms 3064 KB
31_large_increasing01 WA 816 ms 54520 KB
31_large_increasing02 WA 2076 ms 105848 KB
32_large_decreasing00 AC 31 ms 3064 KB
32_large_decreasing01 AC 825 ms 54520 KB
32_large_decreasing02 AC 2079 ms 105976 KB
33_large_mountain00 AC 35 ms 2108 KB
33_large_mountain01 AC 736 ms 27836 KB
33_large_mountain02 AC 1835 ms 53692 KB
34_large_valley00 AC 35 ms 2108 KB
34_large_valley01 AC 747 ms 27836 KB
34_large_valley02 AC 1829 ms 53692 KB