結果

問題 No.284 門松と魔法(2)
ユーザー koyumeishikoyumeishi
提出日時 2015-09-25 16:00:48
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,441 ms / 5,000 ms
コード長 4,129 bytes
コンパイル時間 1,563 ms
コンパイル使用メモリ 105,504 KB
実行使用メモリ 22,100 KB
最終ジャッジ日時 2023-09-26 15:05:00
合計ジャッジ時間 10,365 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,384 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 2 ms
4,384 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,384 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 3 ms
4,380 KB
testcase_17 AC 2 ms
4,384 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,384 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 4 ms
4,380 KB
testcase_23 AC 53 ms
4,384 KB
testcase_24 AC 584 ms
4,384 KB
testcase_25 AC 215 ms
4,384 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 2 ms
4,384 KB
testcase_29 AC 1,321 ms
12,736 KB
testcase_30 AC 1,033 ms
8,316 KB
testcase_31 AC 117 ms
4,384 KB
testcase_32 AC 1,441 ms
22,084 KB
testcase_33 AC 934 ms
21,984 KB
testcase_34 AC 949 ms
22,100 KB
testcase_35 AC 1 ms
4,384 KB
testcase_36 AC 1 ms
4,380 KB
testcase_37 AC 167 ms
4,380 KB
testcase_38 AC 95 ms
4,384 KB
testcase_39 AC 4 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

struct node{
	int cnt;
	int l;
	int m;
	node():cnt(0),l(0),m(0){}
	bool operator < (const node& x) const{
		return cnt < x.cnt;
	}
	bool operator == (const node& x) const{
		return (cnt == x.cnt) && (l == x.l) && (m == x.m);
	}
};

struct val{
	node a[3];
	val(){
		a[0] = a[1] = a[2] = node();
	}

	val operator +(const val& x){
		val ret;
		vector<node> tmp(6);
		for(int i=0; i<3; i++){
			tmp[2*i] = a[i];
			tmp[2*i+1] = x.a[i];
		}
		sort(tmp.rbegin(), tmp.rend());
		tmp.erase( unique(tmp.begin(), tmp.end()), tmp.end());

		vector<bool> used(tmp.size(),false);
		ret.a[0] = tmp[0];
		used[0] = true;
		for(int i=1; i<tmp.size(); i++){
			if(ret.a[0].l != tmp[i].l){
				ret.a[1] = tmp[i];
				used[i] = true;
				break;
			}	
		}
		int p=0;
		for(int i=1; i<tmp.size(); i++){
			if(used[i]) continue;
			if(p==0){
				ret.a[2] = tmp[i];
				used[i] = true;
				break;
			}
		}
		return ret;
	}
};

ostream& operator << (ostream& os, const node& x){
	os << "{" << x.cnt << ", " << x.l << ", " << x.m << "} ";
	return os;
}


val comp(const val& x, const val& y){
	val ret;
	vector<node> tmp(6);
	for(int i=0; i<3; i++){
		tmp[2*i] = x.a[i];
		tmp[2*i+1] = y.a[i];
	}
	sort(tmp.rbegin(), tmp.rend());
	tmp.erase( unique(tmp.begin(), tmp.end()), tmp.end());
	for(int i=0; i<3 && i<tmp.size(); i++){
		ret.a[i] = tmp[i];
	}
	return ret;
}

val hoge(const val& x, int a){
	val ret;
	int p = 0;
	for(int i=0; i<3; i++){
		if(x.a[i].l != a) ret.a[p++] = x.a[i];
	}
	return ret;
}

class seg{
public:
	vector<val> v;
	int size;
	seg(int n){
		size = 1;
		while(size<n){
			size <<= 1;
		}
		v.resize(2*size);
	}

	void update(int l, int r, val& x, int lb, int ub, int pos){
		if(ub<=l || r<=lb) return;
		if(l<=lb && ub<=r){
			v[pos] = v[pos]+x;
			return;
		}
		update(l,r,x, lb,(lb+ub)/2, pos*2+1);
		update(l,r,x, (lb+ub)/2,ub, pos*2+2);
		v[pos] = v[pos*2+1] + v[pos*2+2];
	}
	void update(int l, int r, val& x){
		update(l,r,x,0,size,0);
	}

	val get(int l, int r, int a, int lb, int ub, int pos){
		if(ub<=l || r<=lb) return val();
		if(l<=lb && ub<=r){
			val ret = hoge(v[pos], a);
			if(ub-lb>1) ret = comp(hoge(v[pos*2+1],a), hoge(v[pos*2+2],a));
			return ret;
		}
		val x;
		x = get(l,r, a, lb,(lb+ub)/2, pos*2+1);

		val y;
		y = get(l,r, a, (lb+ub)/2, ub, pos*2+2);

		val ret = comp(x,y);
		return ret;
	}

	val get(int l, int r, int a){
		return get(l,r, a, 0,size,0);
	}
};

template<class T>
vector<T> compress(vector<T> a, int& size){
	auto b = a;
	sort(b.begin(), b.end());
	b.erase( unique(b.begin(), b.end()), b.end());
	for(int i=0; i<a.size(); i++){
		a[i] = (lower_bound(b.begin(), b.end(), a[i]) - b.begin()) +1;
	}
	size = b.size();
	return a;
}

val func(const val& x, int a){
	//cerr << x << " ";
	val ret;
	for(int i=0; i<3; i++){
		ret.a[i].m = a;
		ret.a[i].cnt = x.a[i].cnt+1;
		ret.a[i].l = x.a[i].m;
	}

	val start;
	start.a[0].cnt = 1;
	start.a[0].m = a;
	start.a[0].l = 1e6;

	return ret+start;
}

#include <ctime>

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i=0; i<n; i++){
		scanf("%d", &a[i]);
	}

	auto start = clock();

	int m;
	a = compress(a, m);

	a.erase( unique(a.begin(), a.end()), a.end());
	n = a.size();

	seg inc(m+1);
	seg dec(m+1);

	for(int i=0; i<n; i++){
		val s = func(inc.get(a[i]+1, m+1, a[i]), a[i]);
		//cerr << s << endl;

		val t = func(dec.get(0, a[i], a[i]), a[i]);
		//cerr << t << endl;

		dec.update(a[i],a[i]+1, s);
		inc.update(a[i],a[i]+1, t);
	}

	int ans = 0;
	val x = inc.get(0,m+1, 1e6);
	val y = dec.get(0,m+1, 1e6);
	for(int i=0; i<3; i++){
		ans = max(ans, x.a[i].cnt);
		ans = max(ans, y.a[i].cnt);
	}
	if(ans <= 2) ans = 0;

	cout << ans << endl;

	cerr << clock()-start << endl;

	return 0;
}






 //   *    *  *   *  *   *   ****            
///   *    *  **  *  *  *   *    *                 
 //   *    *  * * *  * *    *    *    
 //   *    *  * * *  ** *   *    *              
////   ****   *  **  *   *   ****
0