結果
問題 | No.1234 典型RMQ |
ユーザー | aajisaka |
提出日時 | 2020-09-23 23:27:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 7,027 bytes |
コンパイル時間 | 2,600 ms |
コンパイル使用メモリ | 206,108 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-11-09 02:24:50 |
合計ジャッジ時間 | 6,163 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 80 ms
7,040 KB |
testcase_07 | AC | 60 ms
5,248 KB |
testcase_08 | AC | 85 ms
7,168 KB |
testcase_09 | AC | 73 ms
5,248 KB |
testcase_10 | AC | 81 ms
7,040 KB |
testcase_11 | AC | 79 ms
6,784 KB |
testcase_12 | AC | 73 ms
5,248 KB |
testcase_13 | AC | 61 ms
5,248 KB |
testcase_14 | AC | 72 ms
5,248 KB |
testcase_15 | AC | 70 ms
5,248 KB |
testcase_16 | AC | 83 ms
6,912 KB |
testcase_17 | AC | 74 ms
5,248 KB |
testcase_18 | AC | 57 ms
5,248 KB |
testcase_19 | AC | 86 ms
7,168 KB |
testcase_20 | AC | 65 ms
7,168 KB |
testcase_21 | AC | 81 ms
7,040 KB |
testcase_22 | AC | 74 ms
7,296 KB |
testcase_23 | AC | 75 ms
7,168 KB |
testcase_24 | AC | 74 ms
7,040 KB |
testcase_25 | AC | 74 ms
7,168 KB |
testcase_26 | AC | 75 ms
7,040 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
ソースコード
/*** code generated by JHelper* More info: https://github.com/AlexeyDmitriev/JHelper* @author aajisaka*/#include<bits/stdc++.h>using namespace std;void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}#ifdef LOCAL#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...) 42#endif#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)#define rep(i,n) for(int i=0; i<(int)(n); i++)#define all(v) v.begin(), v.end()template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }using ll = long long;using ull = unsigned long long;using P = pair<ll, ll>;constexpr long double PI = 3.14159265358979323846264338327950288L;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());#include <algorithm>#include <cassert>#include <iostream>#include <vector>#ifdef _MSC_VER#include <intrin.h>#endifnamespace 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/* sample: range add, range max queryauto op = [](ll a, ll b) { return max(a,b); };auto e = []() { return LLONG_MIN/2; };auto mapping = [](ll a, ll b) { return a+b; };auto composition = [](ll a, ll b) { return a+b; };auto id = []() { return 0LL; };auto seg = lazy_segtree<ll, op, e, ll, mapping, composition, id>(vec);*/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();}};ll op(ll a, ll b) {return min(a, b);}ll e() {return LLONG_MAX/2;}ll mapping(ll a, ll b) {return a+b;}ll composition(ll a, ll b) {return a+b;}ll id() {return 0LL;}class No1234RMQ {public:void solve(istream& cin, ostream& cout) {SPEED;int n; cin >> n;vector<ll> a(n);for(auto& x: a) cin >> x;auto seg = lazy_segtree<ll, op, e, ll, mapping, composition, id>(a);int q; cin >> q;while(q--) {int k, l, r, c; cin >> k >> l >> r >> c;l--; r--;if (k==1) {seg.apply(l, r+1, c);} else {cout << seg.prod(l, r+1) << '\n';}}}};signed main() {No1234RMQ solver;std::istream& in(std::cin);std::ostream& out(std::cout);solver.solve(in, out);return 0;}