結果

問題 No.284 門松と魔法(2)
コンテスト
ユーザー btk
提出日時 2015-10-06 22:08:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,744 bytes
コンパイル時間 691 ms
コンパイル使用メモリ 87,492 KB
実行使用メモリ 73,728 KB
最終ジャッジ日時 2024-07-20 01:45:33
合計ジャッジ時間 6,045 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;


#define input_init stringstream ss; string strtoken, token; istringstream is
#define input_line  getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit)
#define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num

namespace seg_tree{
	typedef pair<int, int> P;
#define st(x) (x).first
#define ed(x) (x).second
#define A_MAX 1000010
#define A_MIN 0
	struct seg_Tree{
		P interval;
		int val;

		int size(){ return(ed(interval) - st(interval) + 1); }
		void set(int s, int t){
			st(interval) = s, ed(interval) = t;
		}
		seg_Tree(){
			val = 0;
			set(1, 0);
		}

	};
	int make_tree(seg_Tree* tree,int k, int s, int t){
		if (s <= t){
			tree[k].set(s, t);
			if (tree[k].size() > 1){
				int l = 2 * k + 1;
				int r = l + 1;
				l = make_tree(tree,l, s, (s + t) / 2);
				r = make_tree(tree,r, (s + t) / 2 + 1, t);
				return tree[k].val = max(l, r);
			}
			else
				return tree[k].val = 0;
		}
		return 0;
	}

	void construct_tree(seg_Tree* tree){
		make_tree(tree,0, A_MIN, A_MAX - 1);
	}

	int find(seg_Tree* tree,int k, P len){
		int l = 2 * k + 1;
		int r = l + 1;
		if (tree[k].interval == len)
			return tree[k].val;
		else if (ed(len) <= ed(tree[l].interval))
			return find(tree,l, len);
		else if ((st(len) >= st(tree[r].interval)))
			return find(tree,r, len);
		else{
			l = find(tree,l, make_pair(st(len), ed(tree[l].interval)));
			if (l < tree[r].val)l = max(l, find(tree,r, make_pair(st(tree[r].interval), ed(len))));
			return l;
		}
	}
	int add(seg_Tree* tree, int k, int key, int val){
		if (tree[k].size() > 1){
			int l = 2 * k + 1;
			int r = l + 1;
			if (key <= ed(tree[l].interval))
				tree[k].val = max(tree[k].val, add(tree, l, key, val));
			else
				tree[k].val = max(tree[k].val, add(tree, r, key, val));
		}
		else
			tree[k].val = max(tree[k].val, val);
		return tree[k].val;
	}



}
using namespace seg_tree;
seg_Tree dp[2][A_MAX*3];

int main(){
	construct_tree(dp[0]);
	construct_tree(dp[1]);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++){
		int A;
		cin >> A;
		int maxi = 0, mini = 0;
		maxi = find(dp[1], 0, make_pair(A + 1, A_MAX - 1))+1;
		mini = find(dp[0], 0, make_pair(A_MIN, A - 1)) + 1;
		add(dp[0], 0, A, maxi);
		add(dp[1], 0, A, mini);
	}
	int res=max(find(dp[0], 0, make_pair(A_MIN, A_MAX - 1)), find(dp[1], 0, make_pair(A_MIN, A_MAX - 1)));
	cout << (res < 3 ? 0 : res) << endl;
}
0