結果
| 問題 | No.284 門松と魔法(2) |
| ユーザー |
 btk
|
| 提出日時 | 2015-10-07 04:41:33 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 4,325 bytes |
| コンパイル時間 | 1,011 ms |
| コンパイル使用メモリ | 103,588 KB |
| 実行使用メモリ | 817,920 KB |
| 最終ジャッジ日時 | 2024-07-20 01:50:20 |
| 合計ジャッジ時間 | 5,589 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
ソースコード
#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;
vector<vector<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.resize(2);
for (auto& i : val){
i.resize(3);
}
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.resize(2);
for (auto& i : tree[k].val){
i.resize(3);
i[0] = A_MIN;
i[1] = st(tree[k].interval);
i[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] == tmp[i])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;
}