結果

問題 No.284 門松と魔法(2)
ユーザー maimai
提出日時 2017-10-19 21:51:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 9,606 bytes
コンパイル時間 3,089 ms
コンパイル使用メモリ 216,648 KB
最終ジャッジ日時 2025-01-05 03:21:01
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other RE * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h" // define macro "/D__MAI"
using namespace std;
typedef long long int ll;
#define xprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) {printf("L%d %s > ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;}
#define debugaa(m,h,w) {printf("L%d %s >\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}}
#define ALL(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(auto cnt=0ll;(cnt)<(l);++(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
#define EPS 1e-12
template<typename T1, typename T2> ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o;
    }
template<typename iterator> inline size_t argmin(iterator begin, iterator end) { return distance(begin, min_element(begin, end)); }
template<typename iterator> inline size_t argmax(iterator begin, iterator end) { return distance(begin, max_element(begin, end)); }
template<typename T> T& maxset(T& to, const T& val) { return to = max(to, val); }
template<typename T> T& minset(T& to, const T& val) { return to = min(to, val); }
mt19937_64 randdev(8901016);
inline ll rand_range(ll l, ll h) {
return uniform_int_distribution<ll>(l, h)(randdev);
}
#ifdef __MAI
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
#ifdef __VSCC
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#endif
namespace {
#define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E)
class MaiScanner {
public:
template<typename T> void input_integer(T& var) {
var = 0;
T sign = 1;
int cc = getchar_unlocked();
for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
if (cc == '-') sign = -1;
for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
var = (var << 3) + (var << 1) + cc - '0';
var = var*sign;
}
inline int c() { return getchar_unlocked(); }
inline MaiScanner& operator>>(int& var) {
input_integer<int>(var);
return *this;
}
inline MaiScanner& operator>>(long long& var) {
input_integer<long long>(var);
return *this;
}
inline MaiScanner& operator>>(string& var) {
int cc = getchar_unlocked();
for (; !isvisiblechar(cc); cc = getchar_unlocked());
for (; isvisiblechar(cc); cc = getchar_unlocked())
var.push_back(cc);
return *this;
}
template<typename IT> void in(IT begin, IT end) {
for (auto it = begin; it != end; ++it) *this >> *it;
}
};
}
MaiScanner scanner;
template<typename T>
//typedef int T;
class segtree {
int size;
vector<T> valdata;
vector<int> addtree;
vector<int> maxtree;
int _geti(const vector<int>& v, int idx) const {
if (size - 1 <= idx) return (idx - size + 1);
// if (idx < 0) return idx;
return v[idx];
}
public:
segtree(int n) {
size = 8;
while (size < n) size <<= 1;
maxtree.resize(size);
valdata.resize(size);
addtree.resize(size);
flat();
}
// tree
void flat() {
for (int i = size - 2; 0 <= i; --i) {
int c = 2 * i + 1;
if (size - 1 <= c) {
maxtree[i] = c - size + 1;
}
else {
maxtree[i] = maxtree[c];
}
}
}
// TODO:verify
// addtree0valdata
void apply(T sum = 0, int ptr = 0) {
if (size - 1 <= ptr) {
valdata[ptr - size + 1] += sum;
}
else {
sum += addtree[ptr];
apply(sum, ptr * 2 + 1);
apply(sum, ptr * 2 + 2);
addtree[ptr] = 0;
}
}
void fill(T val) {
std::fill(valdata.begin(), valdata.end(), val);
std::fill(addtree.begin(), addtree.end(), 0);
flat();
}
// T operator[](int index) const {
//
// }
T getval(int index) const {
T sum = valdata[index];
index += size - 1;
while (0 < index) {
index = (index - 1) / 2; //
sum += addtree[index];
}
return sum;
}
void setval(int index, const T e) {
valdata[index] = e;
for (int i = index + size - 1; 0 < i;) {
i = (i - 1) / 2; //
valdata[index] -= addtree[i];
}
index += size - 1;
while (0 < index) {
index = (index - 1) / 2; //
int c1 = index * 2 + 1;
int c2 = index * 2 + 2;
int i1, i2;
i1 = _geti(maxtree, c1);
i2 = _geti(maxtree, c2);
maxtree[index] = getval(i1) > getval(i2) ? i1 : i2;
}
}
void addvalrange(int begin, int end, const T e, int ptr = 0, int rangebegin = 0, int rangeend = 0) {
if (rangeend <= rangebegin) { rangeend = size; }
if (rangeend <= begin || end <= rangebegin) return;
if (begin <= rangebegin && rangeend <= end) {
if (size - 1 <= ptr)
valdata[ptr - size + 1] += e;
else
addtree[ptr] += e;
return;
}
int rangemid = (rangebegin + rangeend) / 2;
addvalrange(begin, end, e, ptr * 2 + 1, rangebegin, rangemid);
addvalrange(begin, end, e, ptr * 2 + 2, rangemid, rangeend);
int i1, i2;
i1 = _geti(maxtree, ptr * 2 + 1);
i2 = _geti(maxtree, ptr * 2 + 2);
maxtree[ptr] = getval(i1) > getval(i2) ? i1 : i2;
}
int getmaxrangeIdx(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) const {
if (rangeend <= rangebegin) { rangeend = size; }
if (rangeend <= begin || end <= rangebegin) return begin; // note:index
if (begin <= rangebegin && rangeend <= end) return _geti(maxtree, ptr);
int rangemid = (rangebegin + rangeend) / 2;
int l = getmaxrangeIdx(begin, end, ptr * 2 + 1, rangebegin, rangemid);
int r = getmaxrangeIdx(begin, end, ptr * 2 + 2, rangemid, rangeend);
if (getval(l) >= getval(r))
return l;
else
return r;
}
T getmaxrange(int begin, int end) {
return getval(getmaxrangeIdx(begin, end));
}
};
ll m, n, kei;
// LKSS☆3.5
//
// [1,3,1,3,1] => 5 => [WA]
// 2
//
// pair<count, prevprev>
int main() {
abort();
scanner >> n;
vector<int> aa;
aa.reserve(n);
map<int, int> zip;
repeat(i, n) {
int a;
scanner >> a;
aa.push_back(a);
zip[a] = 0;
}
//
{
int c = 0;
for (auto& p : zip)
p.second = c++;
}
for (auto& a : aa)
a = zip[a];
segtree<int> upkado(n); //
segtree<int> dnkado(n); //
repeat(i, n) {
int a = aa[i];
int u = dnkado.getmaxrange(0, a) + 1;
int d = upkado.getmaxrange(a + 1, n) + 1;
if (upkado.getval(a) < u)
upkado.setval(a, u);
if (dnkado.getval(a) < d)
dnkado.setval(a, d);
// repeat(j, n)
// printf("%2d ", upkado.getval(j));
// cout << endl;
// repeat(j, n)
// printf("%2d ", dnkado.getval(j));
// cout << endl;
}
int ans = max(upkado.getval(aa[n - 1]), dnkado.getval(aa[n - 1]));
if (ans <= 2)
cout << 0 << endl;
else
cout << ans << endl;
return 0;
}
/*
LKSS
- - - - - - -
LKSS
x
0
- - - - - - -
x
|x|=1 : x
|x|=2 : x1 < x2
|x|>=3 : x1 < x2
|x|=1 : x
|x|=2 : x1 > x2
|x|>=3 : x1 > x2
2dp
dp1[x] x
dp2[x] x
dp
dp1[x] = max(dp2[1..x-1]) + 1
dp2[x] = max(dp1[x+1..N]) + 1
dpmax(dp1[x_N], dp[x_N])
20
O(logN)
- - - - - - -
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0