結果

問題 No.318 学学学学学
ユーザー firiexp
提出日時 2019-10-29 20:00:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,981 bytes
コンパイル時間 754 ms
コンパイル使用メモリ 90,160 KB
最終ジャッジ日時 2024-11-14 21:48:20
合計ジャッジ時間 1,562 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:17:39: error: '::numeric_limits' has not been declared
   17 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
      |                                       ^~~~~~~~~~~~~~
main.cpp:17:55: error: expected primary-expression before '>' token
   17 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
      |                                                       ^
main.cpp:17:61: error: no matching function for call to 'max()'
   17 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
      |                                                        ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
                 from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
main.cpp:17:61: note:   candidate expects 2 arguments, 0 provided
   17 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
      |                                                        ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:300:5: note: candidate: 'templat

ソースコード

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

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;
template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
template <class M>
struct LazySegmentTree{
using T = typename M::T;
using L = typename M::L;
int sz, height{};
vector<T> seg; vector<L> lazy;
explicit LazySegmentTree(int n) {
sz = 1; while(sz < n) sz <<= 1, height++;
seg.assign(2*sz, M::e());
lazy.assign(2*sz, M::l());
}
void set(int k, const T &x){
seg[k + sz] = x;
}
void build(){
for (int i = sz-1; i > 0; --i) seg[i] = M::f(seg[i<<1], seg[(i<<1)|1]);
}
T reflect(int k){ return lazy[k] == M::l() ? seg[k] : M::g(seg[k], lazy[k]); }
void eval(int k){
if(lazy[k] == M::l()) return;
lazy[(k<<1)|0] = M::h(lazy[(k<<1)|0], lazy[k]);
lazy[(k<<1)|1] = M::h(lazy[(k<<1)|1], lazy[k]);
seg[k] = reflect(k);
lazy[k] = M::l();
}
void thrust(int k){ for (int i = height; i; --i) eval(k>>i); }
void recalc(int k) { while(k >>= 1) seg[k] = M::f(reflect((k<<1)|0), reflect((k<<1)|1));}
void update(int a, int b, const L &x){
thrust(a += sz); thrust(b += sz-1);
for (int l = a, r = b+1;l < r; l >>=1, r >>= 1) {
if(l&1) lazy[l] = M::h(lazy[l], x), l++;
if(r&1) --r, lazy[r] = M::h(lazy[r], x);
}
recalc(a);
recalc(b);
}
T query(int a, int b){ // [l, r)
thrust(a += sz);
thrust(b += sz-1);
T ll = M::e(), rr = M::e();
for(int l = a, r = b+1; l < r; l >>=1, r>>=1) {
if (l & 1) ll = M::f(ll, reflect(l++));
if (r & 1) rr = M::f(reflect(--r), rr);
}
return M::f(ll, rr);
}
};
struct Monoid{
using T = int;
using L = int;
static T f(T a, T b) { return max(a, b); }
static T g(T a, L b) {
return max(a, b);
}
static L h(L a, L b) {
return max(a, b);
}
static T e() { return -INF<int>; }
static L l() { return -INF<int>; }
};
int main() {
int n;
cin >> n;
vector<int> v(n);
for (auto &&i : v) scanf("%d", &i);
auto z = v;
sort(z.begin(), z.end());
z.erase(unique(z.begin(), z.end()), z.end());
auto f = [&z](int x){return lower_bound(z.begin(),z.end(), x) - z.begin(); };
int m = z.size();
vector<int> l(m, INF<int>), r(m, -INF<int>);
for (int i = 0; i < n; ++i) {
int x = f(v[i]);
l[x] = min(l[x], i); r[x] = max(r[x], i);
}
LazySegmentTree<Monoid> seg(n);
for (int i = 0; i < m; ++i) {
seg.update(l[i], r[i]+1, z[i]);
}
for (int i = 0; i < n; ++i) {
if(i) printf(" ");
printf("%d", seg.query(i, i+1));
}
puts("");
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0