結果
| 問題 | No.1234 典型RMQ |
| ユーザー |
 FF256grhy
|
| 提出日時 | 2020-09-18 22:19:43 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 10,699 bytes |
| コンパイル時間 | 2,523 ms |
| コンパイル使用メモリ | 190,704 KB |
| 最終ジャッジ日時 | 2025-01-14 17:21:16 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In instantiation of ‘T vin() [with T = std::array<int, 4>]’:
main.cpp:58:79: required from ‘auto vin(N, M ...) [with T = std::array<int, 4>; N = int; M = {}]’
main.cpp:331:29: required from here
main.cpp:56:44: error: no match for ‘operator>>’ (operand types are ‘std::basic_istream<char>’ and ‘std::array<int, 4>’)
56 | template<typename T> T vin() { T v; (* IS) >> v; return v; }
| ~~~~~~~^~~~
In file included from /usr/include/c++/13/sstream:40,
from /usr/include/c++/13/complex:45,
from /usr/include/c++/13/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127,
from main.cpp:1:
/usr/include/c++/13/istream:325:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
325 | operator>>(void*& __p)
| ^~~~~~~~
/usr/include/c++/13/istream:325:25: note: no known conversion for argument 1 from ‘std::array<int, 4>’ to ‘void*&’
325 | operator>>(void*& __p)
| ~~~~~~~^~~
/usr/include/c++/13/istream:224:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
224 | operator>>(long double& __f)
| ^~~~~~~~
/usr/include/c++/13/istream:224:31: note: no known conversion for argument 1 from ‘std::array<int, 4>’ to ‘long double&’
224 | operator>>(long double& __f)
| ~~~~~~~~~~~~~^~~
/usr/include/c++/13/istream:220:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _Ch
ソースコード
#include <bits/stdc++.h>using namespace std;using LL = long long int;#define incII(i, l, r) for(LL i = (l) ; i <= (r); i++)#define incIX(i, l, r) for(LL i = (l) ; i < (r); i++)#define incXI(i, l, r) for(LL i = (l) + 1; i <= (r); i++)#define incXX(i, l, r) for(LL i = (l) + 1; i < (r); i++)#define decII(i, l, r) for(LL i = (r) ; i >= (l); i--)#define decIX(i, l, r) for(LL i = (r) - 1; i >= (l); i--)#define decXI(i, l, r) for(LL i = (r) ; i > (l); i--)#define decXX(i, l, r) for(LL i = (r) - 1; i > (l); i--)#define inc(i, n) incIX(i, 0, n)#define dec(i, n) decIX(i, 0, n)#define inc1(i, n) incII(i, 1, n)#define dec1(i, n) decII(i, 1, n)auto inII = [](auto x, auto l, auto r) { return (l <= x && x <= r); };auto inIX = [](auto x, auto l, auto r) { return (l <= x && x < r); };auto inXI = [](auto x, auto l, auto r) { return (l < x && x <= r); };auto inXX = [](auto x, auto l, auto r) { return (l < x && x < r); };auto setmin = [](auto & a, auto b) { return (b < a ? a = b, true : false); };auto setmax = [](auto & a, auto b) { return (b > a ? a = b, true : false); };auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };#define PB push_back#define EB emplace_back#define MP make_pair#define MT make_tuple#define FI first#define SE second#define FR front()#define BA back()#define ALL(c) c.begin(), c.end()#define RALL(c) c.rbegin(), c.rend()#define RV(c) reverse(ALL(c))#define SC static_cast#define SI(c) SC<int>(c.size())#define SL(c) SC<LL >(c.size())#define RF(e, c) for(auto & e: c)#define SF(c, ...) for(auto & [__VA_ARGS__]: c)#define until(e) while(! (e))#define if_not(e) if(! (e))#define ef else if#define UR assert(false)auto * IS = & cin;auto * OS = & cout;array<string, 3> SEQ = { "", " ", "" };// inputtemplate<typename T> T in() { T a; (* IS) >> a; return a; }// input: tupletemplate<typename U, int I> void tin_([[maybe_unused]] U & t) { }template<typename U, int I, typename A, typename ... B> void tin_(U & t) { (* IS) >> get<I>(t); tin_<U, I + 1, B ...>(t); }template<typename ... T> auto tin() { tuple<T ...> t; tin_<tuple<T ...>, 0, T ...>(t); return t; }// input: arraytemplate<typename T, int N> auto ain() { array<T, N> a; inc(i, N) { (* IS) >> a[i]; } return a; }// input: multi-dimensional vectortemplate<typename T> T vin() { T v; (* IS) >> v; return v; }template<typename T, typename N, typename ... M> auto vin(N n, M ... m) {vector<decltype(vin<T, M ...>(m ...))> v(n); inc(i, n) { v[i] = vin<T, M ...>(m ...); } return v;}// input: multi-column (tuple<vector>)template<typename U, int I> void colin_([[maybe_unused]] U & t) { }template<typename U, int I, typename A, typename ... B> void colin_(U & t) {get<I>(t).PB(in<A>()); colin_<U, I + 1, B ...>(t);}template<typename ... T> auto colin(int n) {tuple<vector<T> ...> t; inc(i, n) { colin_<tuple<vector<T> ...>, 0, T ...>(t); } return t;}// outputvoid out_([[maybe_unused]] string s) { }template<typename A> void out_([[maybe_unused]] string s, A && a) { (* OS) << a; }template<typename A, typename ... B> void out_(string s, A && a, B && ... b) { (* OS) << a << s; out_(s, b ...); }auto outF = [](auto x, auto y, auto z, auto ... a) { (* OS) << x; out_(y, a ...); (* OS) << z << flush; };auto out = [](auto ... a) { outF("", " " , "\n", a ...); };auto outS = [](auto ... a) { outF("", " " , " " , a ...); };auto outL = [](auto ... a) { outF("", "\n", "\n", a ...); };auto outN = [](auto ... a) { outF("", "" , "" , a ...); };// output: multi-dimensional vectortemplate<typename T> ostream & operator<<(ostream & os, vector<T> const & v) {os << SEQ[0]; inc(i, SI(v)) { os << (i == 0 ? "" : SEQ[1]) << v[i]; } return (os << SEQ[2]);}template<typename T> void vout_(T && v) { (* OS) << v; }template<typename T, typename A, typename ... B> void vout_(T && v, A a, B ... b) {inc(i, SI(v)) { (* OS) << (i == 0 ? "" : a); vout_(v[i], b ...); }}template<typename T, typename A, typename ... B> void vout (T && v, A a, B ... b) { vout_(v, a, b ...); (* OS) << a << flush; }template<typename T, typename A, typename ... B> void voutN(T && v, A a, B ... b) { vout_(v, a, b ...); (* OS) << flush; }// ---- ----#include <algorithm>#ifdef _MSC_VER#include <intrin.h>#endifnamespace atcoder {namespace internal {// @param n `0 <= n`// @return minimum non-negative `x` s.t. `n <= 2**x`int ceil_pow2(int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}// @param n `1 <= n`// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`int bsf(unsigned int n) {#ifdef _MSC_VERunsigned long index;_BitScanForward(&index, n);return index;#elsereturn __builtin_ctz(n);#endif}} // namespace internal} // namespace atcoder#include <cassert>#include <iostream>#include <vector>namespace atcoder {template <class S,S (*op)(S, S),S (*e)(),class F,S (*mapping)(F, S),F (*composition)(F, F),F (*id)()>struct lazy_segtree {public:lazy_segtree() : lazy_segtree(0) {}lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {log = internal::ceil_pow2(_n);size = 1 << log;d = std::vector<S>(2 * size, e());lz = std::vector<F>(size, id());for (int i = 0; i < _n; i++) d[size + i] = v[i];for (int i = size - 1; i >= 1; i--) {update(i);}}void set(int p, S x) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);d[p] = x;for (int i = 1; i <= log; i++) update(p >> i);}S get(int p) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);return d[p];}S prod(int l, int r) {assert(0 <= l && l <= r && r <= _n);if (l == r) return e();l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push(r >> i);}S sml = e(), smr = e();while (l < r) {if (l & 1) sml = op(sml, d[l++]);if (r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_prod() { return d[1]; }void apply(int p, F f) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);d[p] = mapping(f, d[p]);for (int i = 1; i <= log; i++) update(p >> i);}void apply(int l, int r, F f) {assert(0 <= l && l <= r && r <= _n);if (l == r) return;l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}{int l2 = l, r2 = r;while (l < r) {if (l & 1) all_apply(l++, f);if (r & 1) all_apply(--r, f);l >>= 1;r >>= 1;}l = l2;r = r2;}for (int i = 1; i <= log; i++) {if (((l >> i) << i) != l) update(l >> i);if (((r >> i) << i) != r) update((r - 1) >> i);}}template <bool (*g)(S)> int max_right(int l) {return max_right(l, [](S x) { return g(x); });}template <class G> int max_right(int l, G g) {assert(0 <= l && l <= _n);assert(g(e()));if (l == _n) return _n;l += size;for (int i = log; i >= 1; i--) push(l >> i);S sm = e();do {while (l % 2 == 0) l >>= 1;if (!g(op(sm, d[l]))) {while (l < size) {push(l);l = (2 * l);if (g(op(sm, d[l]))) {sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while ((l & -l) != l);return _n;}template <bool (*g)(S)> int min_left(int r) {return min_left(r, [](S x) { return g(x); });}template <class G> int min_left(int r, G g) {assert(0 <= r && r <= _n);assert(g(e()));if (r == 0) return 0;r += size;for (int i = log; i >= 1; i--) push((r - 1) >> i);S sm = e();do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!g(op(d[r], sm))) {while (r < size) {push(r);r = (2 * r + 1);if (g(op(d[r], sm))) {sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while ((r & -r) != r);return 0;}private:int _n, size, log;std::vector<S> d;std::vector<F> lz;void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }void all_apply(int k, F f) {d[k] = mapping(f, d[k]);if (k < size) lz[k] = composition(f, lz[k]);}void push(int k) {all_apply(2 * k, lz[k]);all_apply(2 * k + 1, lz[k]);lz[k] = id();}};} // namespace atcoderusing namespace atcoder;#define UQnoS(v) v.erase(unique(ALL(v)), v.end())#define UQ(v) sort(ALL(v)); UQnoS(v)#define LB(v, x) (lower_bound(ALL(v), x) - v.begin())#define UB(v, x) (upper_bound(ALL(v), x) - v.begin())// input/output arraytemplate<typename T, size_t N> istream & operator>>(istream & is, array<T, N> & a) { RF(e, a) { is >> e; } return is; }template<typename T, size_t N> ostream & operator<<(ostream & os, array<T, N> const & a) {os << SEQ[0]; inc(i, SI(a)) { os << (i == 0 ? "" : SEQ[1]) << a[i]; } return (os << SEQ[2]);}using S = LL;S op(S a, S b) { return min(a, b); }S e() { return 1e18; }using F = LL;F ap(F f, S a) { return a + f; }F cp(F g, F f) { return f + g; }F id() { return 0; }int main() {auto n = in<int>();auto a = vin<S>(n);auto q = in<int>();auto Q = vin<array<int, 4>>(q);vector<LL> v = { 0, n };lazy_segtree<S, op, e, F, ap, cp, id> st(a);SF(Q, k, l, r, c) {l--;if(k == 1) { st.apply(l, r, c); }if(k == 2) { out(st.prod(l, r)); }}}