結果

問題 No.284 門松と魔法(2)
ユーザー btkbtk
提出日時 2015-10-07 04:45:25
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,316 bytes
コンパイル時間 1,027 ms
コンパイル使用メモリ 97,928 KB
実行使用メモリ 190,976 KB
最終ジャッジ日時 2024-07-20 01:50:33
合計ジャッジ時間 9,538 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
190,848 KB
testcase_01 AC 76 ms
190,792 KB
testcase_02 AC 75 ms
190,688 KB
testcase_03 AC 85 ms
190,848 KB
testcase_04 AC 77 ms
190,872 KB
testcase_05 AC 76 ms
190,848 KB
testcase_06 WA -
testcase_07 AC 75 ms
190,976 KB
testcase_08 AC 78 ms
190,784 KB
testcase_09 AC 79 ms
190,848 KB
testcase_10 AC 77 ms
190,776 KB
testcase_11 AC 77 ms
190,744 KB
testcase_12 AC 78 ms
190,936 KB
testcase_13 AC 76 ms
190,848 KB
testcase_14 AC 77 ms
190,796 KB
testcase_15 AC 78 ms
190,800 KB
testcase_16 AC 78 ms
190,904 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 76 ms
190,848 KB
testcase_20 AC 81 ms
190,848 KB
testcase_21 AC 78 ms
190,804 KB
testcase_22 AC 78 ms
190,848 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 75 ms
190,816 KB
testcase_27 AC 76 ms
190,976 KB
testcase_28 AC 77 ms
190,848 KB
testcase_29 AC 660 ms
190,948 KB
testcase_30 AC 520 ms
190,736 KB
testcase_31 WA -
testcase_32 AC 652 ms
190,848 KB
testcase_33 AC 419 ms
190,796 KB
testcase_34 AC 462 ms
190,848 KB
testcase_35 AC 76 ms
190,680 KB
testcase_36 AC 77 ms
190,848 KB
testcase_37 AC 387 ms
190,976 KB
testcase_38 WA -
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

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
vector<vector<int>> tmp(4,vector<int>(3));
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[2][3];
		int size(){ return(ed(interval) - st(interval) + 1); }
		void set(int s, int t){
			st(interval) = s, ed(interval) = t;
		}
		seg_Tree(){
			set(1, 0);
		}

	};
	void 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;
				make_tree(tree,l, s, (s + t) / 2);
				make_tree(tree,r, (s + t) / 2 + 1, t);

			}
		}
		for (int i = 0; i < 2; i++){
			int* it = tree[k].val[i];
			it[0] = A_MIN;
			it[1] = st(tree[k].interval);
			it[2] = -1;
		}
		return;
	}

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

	P find(seg_Tree* tree,int k, P len,int p){
		if (ed(len) < st(len))return make_pair(-A_MAX, -1);
		int l = 2 * k + 1;
		int r = l + 1;
		if (tree[k].interval == len){
			if (tree[k].val[0][2]!=p)
				return make_pair(tree[k].val[0][0],tree[k].val[0][1]);
			else
				return make_pair(tree[k].val[1][0], tree[k].val[1][1]);
		}
		else if (ed(len) <= ed(tree[l].interval))
			return find(tree,l, len,p);
		else if ((st(len) >= st(tree[r].interval)))
			return find(tree,r, len,p);
		else{
			P L = find(tree,l, make_pair(st(len), ed(tree[l].interval)),p);
			P R=find(tree,r, make_pair(st(tree[r].interval), ed(len)),p);
			return max(L,R);
		}
	}

	seg_Tree add(seg_Tree* tree, int k, int key, P val,P prev){

		if (tree[k].size() > 1){
			int l = 2 * k + 1;
			int r = l + 1;
			seg_Tree rec;
			if (key <= ed(tree[l].interval))
				rec = add(tree, l, key, val,prev);
			else
				rec = add(tree, r, key, val,prev);
			for (int i = 0; i < 2; i++)
				for (int j = 0; j < 3; j++){
					tmp[i][j] = tree[k].val[i][j];
					tmp[i + 2][j] = rec.val[i][j];
				}
			sort(tmp.begin(), tmp.end());
			for (int j = 0; j < 3; j++)tree[k].val[0][j] = tmp[3][j];
			int i = 2;
			while (tree[k].val[0][0] == tmp[i][0] && tree[k].val[0][1] == tmp[i][1] && tree[k].val[0][2] == tmp[i][2])i--;
			for (int j = 0; j < 3; j++)tree[k].val[1][j] = tmp[i][j];
			
		}
		else{
			tree[k].val[0][1] = tree[k].val[1][1] = key;
			tree[k].val[0][0] = val.first;
			tree[k].val[1][0] = val.second;
			tree[k].val[0][2] = prev.first;
			tree[k].val[1][2] = prev.second;

		}
		return tree[k];
	}



}
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;
	add(dp[0], 0, A_MIN, make_pair(0, -A_MAX), make_pair(A_MIN-1, A_MIN - 2));
	add(dp[1], 0, A_MAX - 1, make_pair(0, -A_MAX), make_pair(A_MAX-1, 1 ));
	for (int i = 0; i < N; i++){
		int A;
		cin >> A;
		P maxi1, mini1,maxi2,mini2;
		maxi1 = find(dp[1], 0, make_pair(A + 1, A_MAX - 1),A);
		mini1 = find(dp[0], 0, make_pair(A_MIN, A - 1),A);
//		printf("%d,%d %d,%d\n", A + 1, maxi1.second - 1, maxi1.second + 1, A_MAX - 1);

		maxi2 = max(find(dp[1], 0, make_pair(A + 1, maxi1.second-1), A), find(dp[1], 0, make_pair(maxi1.second+1, A_MAX - 1), A));
	//	printf("%d,%d %d,%d\n", A_MIN, mini1.second - 1, mini1.second + 1, A - 1);
		mini2 = max(find(dp[0], 0, make_pair(A_MIN, mini1.second - 1), A), find(dp[0], 0, make_pair(mini1.second + 1, A - 1), A));
		add(dp[0], 0, A, make_pair(maxi1.first+1, maxi2.first+1), make_pair(maxi1.second, maxi2.second));
		add(dp[1], 0, A, make_pair(mini1.first+1, mini2.first+1), make_pair(mini1.second, mini2.second));
	}
	P res=max(find(dp[0], 0, make_pair(A_MIN, A_MAX - 1),A_MAX), find(dp[1], 0, make_pair(A_MIN, A_MAX - 1),A_MAX));
	cout << (res.first < 3 ? 0 : res.first) << endl;
}
0