#61261 (C++11) No.284 門松と魔法(2)

提出ソース

結果

問題	No.284 門松と魔法(2)
ユーザー	pekempey
提出日時	2015-11-29 04:22:15
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	1,363 ms / 5,000 ms
コード長	4,129 bytes
コンパイル時間	1,885 ms
コンパイル使用メモリ	176,672 KB
実行使用メモリ	16,208 KB
最終ジャッジ日時	2023-10-12 05:37:39
合計ジャッジ時間	10,966 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 15,368 KB
testcase_01	AC	7 ms 15,448 KB
testcase_02	AC	7 ms 15,508 KB
testcase_03	AC	8 ms 15,412 KB
testcase_04	AC	7 ms 15,440 KB
testcase_05	AC	7 ms 15,564 KB
testcase_06	AC	7 ms 15,360 KB
testcase_07	AC	7 ms 15,572 KB
testcase_08	AC	7 ms 15,360 KB
testcase_09	AC	7 ms 15,556 KB
testcase_10	AC	9 ms 15,516 KB
testcase_11	AC	7 ms 15,496 KB
testcase_12	AC	9 ms 15,360 KB
testcase_13	AC	7 ms 15,368 KB
testcase_14	AC	8 ms 15,540 KB
testcase_15	AC	8 ms 15,548 KB
testcase_16	AC	8 ms 15,544 KB
testcase_17	AC	8 ms 15,408 KB
testcase_18	AC	9 ms 15,384 KB
testcase_19	AC	7 ms 15,556 KB
testcase_20	AC	7 ms 15,424 KB
testcase_21	AC	8 ms 15,552 KB
testcase_22	AC	10 ms 15,388 KB
testcase_23	AC	80 ms 15,492 KB
testcase_24	AC	926 ms 15,880 KB
testcase_25	AC	368 ms 15,692 KB
testcase_26	AC	7 ms 15,412 KB
testcase_27	AC	7 ms 15,492 KB
testcase_28	AC	7 ms 15,672 KB
testcase_29	AC	1,313 ms 16,192 KB
testcase_30	AC	952 ms 16,056 KB
testcase_31	AC	445 ms 16,124 KB
testcase_32	AC	1,363 ms 16,144 KB
testcase_33	AC	458 ms 16,208 KB
testcase_34	AC	508 ms 16,080 KB
testcase_35	AC	7 ms 15,500 KB
testcase_36	AC	7 ms 15,504 KB
testcase_37	AC	532 ms 16,064 KB
testcase_38	AC	355 ms 15,984 KB
testcase_39	AC	13 ms 15,408 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
	if (ans <= 2) ans = 0;
	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード