結果

問題 No.284 門松と魔法(2)
ユーザー pekempeypekempey
提出日時 2015-11-29 04:21:40
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,161 bytes
コンパイル時間 1,749 ms
コンパイル使用メモリ 182,176 KB
実行使用メモリ 16,392 KB
最終ジャッジ日時 2024-09-14 05:03:31
合計ジャッジ時間 10,419 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

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;

const int inf = 1e9;
typedef tuple<int, int, int> P3;
typedef pair<P3, P3> P; // (max1, l1, m1), (max2, l2, m2)
const P3 e3(-inf, -1, -1);
const P e(e3, e3);

struct SegmentTree {
	vector<P> mx;
	int size;
	SegmentTree(int n) {
		size = 1;
		while (size < n) size *= 2;
		mx.resize(size * 2, e);
	}

	P merge(P a, P b) {
		P3 x[4] = {a.first, a.second, b.first, b.second};
		sort(x, x + 4);
		if (get<1>(x[2]) != get<1>(x[3])) return P(x[3], x[2]);
		if (get<1>(x[1]) != get<1>(x[3])) return P(x[3], x[1]);
		return P(x[3], x[0]);
	}

	void update(int k, int l, int v) {
		k += size - 1;
		mx[k] = merge(mx[k], {P3(v, l, k - size + 1), P3(-inf, -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);
	}
};

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1, T2> p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}

void update(SegmentTree &st, int r, tuple<int, int, int> t) {
	if (get<1>(t) == -1) return;
	if (get<1>(t) != r) {
		st.update(r, get<2>(t), get<0>(t) + 1);
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep (i, n) cin >> a[i];
	vector<int> ca(a);
	ca.push_back(0);
	ca.push_back(inf);
	sort(ca.begin(), ca.end());
	ca.erase(unique(ca.begin(), ca.end()), ca.end());
	int lb = 0, ub = ca.size() - 1;

	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);
		auto maxinc = inctr.query(r + 1, inctr.size);
		tuple<int, int, int> incz(e3), decz(e3);
		pair<tuple<int, int, int>, tuple<int, int, int>> incx(e), incy(e), decx(e), decy(e);
		if (get<1>(maxdec.first) != r) {
			incz = maxdec.first;
			int mid = get<2>(incz);
			if (mid != -1) {
				incx = dectr.query(0, mid);
				incy = dectr.query(mid + 1, r);
			}
		} else {
			incz = maxdec.second;
			int mid = get<2>(incz);
			if (mid != -1) {
				incx = dectr.query(0, mid);
				incy = dectr.query(mid + 1, r);
			}
		}
		// 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)
		if (get<1>(maxinc.first) != r) {
			decz = maxinc.first;
			int mid = get<2>(decz);
			if (mid != -1) {
				decx = inctr.query(r + 1, mid);
				decy = inctr.query(mid + 1, inctr.size);
			}
		} else {
			decz = maxinc.second;
			int mid = get<2>(decz);
			if (mid != -1) {
				decx = inctr.query(r + 1, mid);
				decy = inctr.query(mid + 1, inctr.size);
			}
		}
		update(inctr, r, incz);
		update(inctr, r, incx.first);
		update(inctr, r, incx.second);
		update(inctr, r, incy.first);
		update(inctr, r, incy.second);
		update(dectr, r, decz);
		update(dectr, r, decx.first);
		update(dectr, r, decx.second);
		update(dectr, r, decy.first);
		update(dectr, r, decy.second);
		inctr.update(r, lb, 1);
		dectr.update(r, ub, 1);
	}

	int x = get<0>(inctr.query(0, inctr.size).first);
	int y = get<0>(dectr.query(0, dectr.size).first);
	int ans = max(x, y);
	cout << x << " " << y << endl;
	if (ans <= 2) ans = 0;
	cout << ans << endl;
	return 0;
}
0