結果

問題 No.284 門松と魔法(2)
コンテスト
ユーザー pekempey
提出日時 2015-11-29 02:37:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,647 bytes
コンパイル時間 1,559 ms
コンパイル使用メモリ 174,544 KB
実行使用メモリ 12,212 KB
最終ジャッジ日時 2024-09-14 05:03:20
合計ジャッジ時間 5,534 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

struct SegmentTree {
	typedef pair<pair<int, int>, pair<int, int>> P; // (max1, l1, m1), (max2, m2, m2)
	vector<P> mx;
	int size;
	P e;
	SegmentTree(int n) {
		size = 1;
		e = {{0, -1}, {0, -1}};
		while (size < n) size *= 2;
		mx.resize(size * 2, e);
	}

	P merge(P a, P b) {
		pair<int, int> x[4] = {a.first, a.second, b.first, b.second};
		sort(x, x + 4);
		return P(x[3], x[2]);
	}

	void update(int k, int p, int v) {
		k += size - 1;
		mx[k] = merge(mx[k], {{v, p}, {-1, -1}});
		while (k > 0) {
			k = (k - 1) / 2;
			mx[k] = merge(mx[k * 2 + 1], mx[k * 2 + 2]);
		}
	}

	P query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return e;
		if (a <= l && r <= b) return mx[k];
		auto x = query(a, b, k * 2 + 1, l, (l + r) / 2);
		auto y = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return merge(x, y);
	}

	P query(int a, int b) {
		return query(a, b, 0, 0, size);
	}
};

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep (i, n) cin >> a[i];
	vector<int> ca(a);
	sort(ca.begin(), ca.end());
	ca.erase(unique(ca.begin(), ca.end()), ca.end());

	rep (i, n) a[i] = lower_bound(ca.begin(), ca.end(), a[i]) - ca.begin();
	SegmentTree inctr(101010), dectr(101010);

	rep (i, n) {
		int r = a[i];
		// dpinc[m][r] = max(dpdec[m+1..][..r-1])
		// =>
		// dpinc[m][r] = max(dpdec[..][..r-1])
		// dpinc[..r-1][r] = max(dpdec[..][..r-1])
		// dp[..r-1][r] = query: [..r-1] => (max,l)
		auto maxdec = dectr.query(0, r);
		if (maxdec.first.second != r) {
			inctr.update(r, r, maxdec.first.first + 1);
		} else {
			inctr.update(r, r, maxdec.second.first + 1);
		}
		// dpdec[m][r] = max(dpinc[..m-1][r+1..])
		// =>
		// dpdec[m][r] = max(dpinc[..][r+1..])
		// dpdec[r+1..][r] = max(dpinc[..][r+1..])
		// dp[r+1..][r] = query: [..r+1] => (max,l)
		auto maxinc = inctr.query(r + 1, inctr.size);
		if (maxinc.first.second != r) {
			dectr.update(r, r, maxinc.first.first + 1);
		} else {
			dectr.update(r, r, maxinc.second.first + 1);
		}
	}

	int ans = 0;
	ans = max(ans, inctr.query(0, inctr.size).first.first);
	ans = max(ans, dectr.query(0, dectr.size).first.first);
	cout << ans << endl;
	return 0;
}
0