Submission #64666

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define eFOR(i,a,n) for(int i=(a);i<=(n);++i)
#define rFOR(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define erFOR(i,a,n) for(int i=(n);i>=(a);--i)
#define SORT(a) sort(a.begin(),a.end())
#define rSORT(a) sort(a.rbegin(),a.rend())
#define fSORT(a,f) sort(a.begin(),a.end(),f)
#define all(a) a.begin(),a.end()
#define out(y,x) ((y)<0||h<=(y)||(x)<0||w<=(x))
#define tp(a,i) get<i>(a)
#define line cout << "-----------------------------\n"
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T, class... Ts>inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline void print(const vector<vector<T>>& v) { for (auto& a : v)print(a); }
inline string reversed(const string& s) { string t = s; reverse(all(t)); return t; }
template<class T>inline T sum(const vector<T>& a, int l, int r) { return a[r] - (l == 0 ? 0 : a[l - 1]); }
template<class T>inline void END(T s) { print(s); exit(0); }
void END() { exit(0); }
template<class Op> class SegmentTree {
using T = typename Op::T;
int len, n;
vector<T> dat;
public:
SegmentTree(const int _n) : n(_n) {
for (len = 1; len < n; len <<= 1);
dat.resize(len << 1, Op::unit);
}
SegmentTree(const vector<T>& v) : n(v.size()) {
for (len = 1; len < n; len <<= 1);
dat.resize(len << 1, Op::unit);
for (int i = 0; i < n; ++i)dat[i + len] = v[i];
for (int i = len - 1; 0 < i; --i)
dat[i] = Op::merge(dat[i << 1], dat[i << 1 | 1]);
}
inline void update(int idx, const T a) {
idx += len;
dat[idx] = Op::update(dat[idx], a);
for (idx >>= 1; 0 < idx; idx >>= 1)
dat[idx] = Op::merge(dat[idx << 1], dat[idx << 1 | 1]);
}
inline T value(int l, int r) {
T vl = Op::unit, vr = Op::unit;
for (l += len, r += len; l < r; l >>= 1, r >>= 1) {
if (l & 1)vl = Op::merge(vl, dat[l++]);
if (r & 1)vr = Op::merge(dat[--r], vr);
}
return Op::merge(vl, vr);
}
inline T operator[](int idx) { return dat[idx + len]; }
};
template<class Type> struct node {
using T = Type;
inline static T unit = 0;
inline static T merge(T vl, T vr) { return max(vl, vr); }
inline static T update(T vl, T vr) { return vr; }
};
int main() {
init();
int n; cin >> n;
VI a(n); cin >> a;
map<int, int> m;
FOR(i, 0, n)m[a[i]];
{
int i = 0;
for (auto it = m.begin(); it != m.end(); ++it)
it->second = i++;
}
FOR(i, 0, n)a[i] = m[a[i]];
int s = m.size();
VI l(n), r(n);
{
SegmentTree<node<int>> dp(s);
FOR(i, 0, n) {
l[i] = dp.value(0, a[i]) + 1;
dp.update(a[i], l[i]);
}
}
{
SegmentTree<node<int>> dp(s);
rFOR(i, 0, n) {
r[i] = dp.value(0, a[i]) + 1;
dp.update(a[i], r[i]);
}
}
int ans = 0;
FOR(i, 0, n)chmax(ans, l[i] + r[i] - 1);
print(ans);
return 0;
}

ステータス

項目 データ
問題 1418 - 山形数列
ユーザー名 ir_1st_vil
投稿日時 2020-11-09 21:12:07
言語 C++17
状態 Accepted
得点 1
ソースコード長 4549 Byte
最大実行時間 209 ms
最大メモリ使用量 64720 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 105 ms 7772 KB
1
in02.txt AC 30 ms 2096 KB
1
in03.txt AC 171 ms 14284 KB
1
in04.txt AC 189 ms 18816 KB
1
in05.txt AC 188 ms 20732 KB
1
in06.txt AC 189 ms 22648 KB
1
in07.txt AC 209 ms 24564 KB
1
in08.txt AC 173 ms 26348 KB
1
in09.txt AC 147 ms 28392 KB
1
in10.txt AC 154 ms 30312 KB
1
in11.txt AC 118 ms 32352 KB
1
in12.txt AC 138 ms 34268 KB
1
in13.txt AC 117 ms 36184 KB
1
in14.txt AC 120 ms 38104 KB
1
in15.txt AC 117 ms 40144 KB
1
in16.txt AC 145 ms 41980 KB
1
in17.txt AC 120 ms 43896 KB
1
in18.txt AC 122 ms 45940 KB
1
in19.txt AC 126 ms 47856 KB
1
in20.txt AC 147 ms 49772 KB
1
in21.txt AC 158 ms 51820 KB
1
in22.txt AC 119 ms 53608 KB
1
in23.txt AC 161 ms 55524 KB
1
in24.txt AC 44 ms 46048 KB
1
in25.txt AC 38 ms 48252 KB
1
in26.txt AC 40 ms 49308 KB
1
in27.txt AC 43 ms 47032 KB
1
in28.txt AC 39 ms 46992 KB
1
in29.txt AC 26 ms 46948 KB
1
in30.txt AC 20 ms 47160 KB
1
in31.txt AC 16 ms 47112 KB
1
in32.txt AC 21 ms 47064 KB
1
in33.txt AC 25 ms 47144 KB
1
in34.txt AC 25 ms 47228 KB
1
in35.txt AC 145 ms 62800 KB
1
in36.txt AC 134 ms 64720 KB
1
sample01.txt AC 25 ms 50892 KB
1
sample02.txt AC 15 ms 50972 KB
1