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

提出ソース

結果

問題	No.284 門松と魔法(2)
ユーザー	btk
提出日時	2015-10-07 04:06:06
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	4,528 bytes
コンパイル時間	1,102 ms
コンパイル使用メモリ	97,984 KB
実行使用メモリ	190,976 KB
最終ジャッジ日時	2024-07-20 01:50:14
合計ジャッジ時間	13,170 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	164 ms 190,848 KB
testcase_01	AC	160 ms 190,976 KB
testcase_02	AC	162 ms 190,720 KB
testcase_03	AC	161 ms 190,848 KB
testcase_04	WA	-
testcase_05	AC	169 ms 190,848 KB
testcase_06	WA	-
testcase_07	AC	166 ms 190,848 KB
testcase_08	AC	164 ms 190,976 KB
testcase_09	AC	163 ms 190,848 KB
testcase_10	AC	162 ms 190,848 KB
testcase_11	AC	167 ms 190,848 KB
testcase_12	AC	169 ms 190,848 KB
testcase_13	AC	171 ms 190,720 KB
testcase_14	AC	166 ms 190,848 KB
testcase_15	AC	164 ms 190,720 KB
testcase_16	AC	166 ms 190,976 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	164 ms 190,848 KB
testcase_20	AC	164 ms 190,848 KB
testcase_21	AC	163 ms 190,848 KB
testcase_22	AC	166 ms 190,848 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	169 ms 190,848 KB
testcase_27	AC	171 ms 190,976 KB
testcase_28	AC	172 ms 190,976 KB
testcase_29	AC	675 ms 190,848 KB
testcase_30	WA	-
testcase_31	WA	-
testcase_32	AC	683 ms 190,848 KB
testcase_33	AC	449 ms 190,848 KB
testcase_34	AC	501 ms 190,848 KB
testcase_35	AC	166 ms 190,848 KB
testcase_36	AC	165 ms 190,848 KB
testcase_37	AC	406 ms 190,848 KB
testcase_38	WA	-
testcase_39	WA	-

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

ソースコード

raw source code

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

			}
		}
		tree[k].val[0] = tree[k].val[1] =-A_MAX;
		tree[k].prev[0] = -3;
		tree[k].prev[1] = -4;
		tree[k].key[0] = -1;
		tree[k].key[1] = -2;
		
		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(0, 0);
		int l = 2 * k + 1;
		int r = l + 1;
		if (tree[k].interval == len){
			if (tree[k].prev[0]!=p)
				return make_pair(tree[k].val[0],tree[k].key[0]);
			else
				return make_pair(tree[k].val[1], tree[k].key[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);
			tmp[0][0] = tree[k].val[0];
			tmp[0][1] = tree[k].key[0];
			tmp[0][2] = tree[k].prev[0];
			tmp[1][0] = tree[k].val[1];
			tmp[1][1] = tree[k].key[1];
			tmp[1][2] = tree[k].prev[1];
			tmp[2][0] = rec.val[0];
			tmp[2][1] = rec.key[0];
			tmp[2][2] =rec.prev[0];
			tmp[3][0] = rec.val[1];
			tmp[3][1] = rec.key[1];
			tmp[3][2] =rec.prev[1];
			sort(tmp.begin(), tmp.end());
			tree[k].val[0] = tmp[3][0];
			tree[k].key[0] = tmp[3][1];
			tree[k].prev[0] = tmp[3][2];
			tree[k].val[1] = tmp[2][0];
			tree[k].key[1] = tmp[2][1];
			tree[k].prev[1] = tmp[2][2];
		}
		else{
			tree[k].key[0] = tree[k].key[1] = key;
			tree[k].val[0] = val.first;
			tree[k].val[1] = val.second;
			tree[k].prev[0] = prev.first;
			tree[k].prev[1] = 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, A_MIN - 1));
	add(dp[1], 0, A_MAX - 1, make_pair(0, -A_MAX), make_pair(A_MAX-1, A_MAX ));
	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;
}

yukicoder

結果

テストケース

ソースコード