結果
問題 | No.1234 典型RMQ |
ユーザー | uchiiii |
提出日時 | 2020-09-19 03:01:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 6,146 bytes |
コンパイル時間 | 3,856 ms |
コンパイル使用メモリ | 239,808 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-11-15 05:00:57 |
合計ジャッジ時間 | 8,717 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 157 ms
8,960 KB |
testcase_07 | AC | 114 ms
5,248 KB |
testcase_08 | AC | 162 ms
9,600 KB |
testcase_09 | AC | 137 ms
6,400 KB |
testcase_10 | AC | 158 ms
9,344 KB |
testcase_11 | AC | 151 ms
8,832 KB |
testcase_12 | AC | 138 ms
6,272 KB |
testcase_13 | AC | 116 ms
5,248 KB |
testcase_14 | AC | 139 ms
6,272 KB |
testcase_15 | AC | 132 ms
6,016 KB |
testcase_16 | AC | 158 ms
9,216 KB |
testcase_17 | AC | 138 ms
6,400 KB |
testcase_18 | AC | 104 ms
5,248 KB |
testcase_19 | AC | 164 ms
9,472 KB |
testcase_20 | AC | 86 ms
9,728 KB |
testcase_21 | AC | 153 ms
8,960 KB |
testcase_22 | AC | 112 ms
9,600 KB |
testcase_23 | AC | 112 ms
9,600 KB |
testcase_24 | AC | 112 ms
9,600 KB |
testcase_25 | AC | 112 ms
9,600 KB |
testcase_26 | AC | 112 ms
9,600 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 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("03") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; using ld = long double; using ll = long long; using ull = unsigned long long; #define endl "\n" #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define rep(i, n) for (int i = 0; i < (n); i++) #define PII pair<int, int> #define PLL pair<ll, ll> #define ALL(x) (x).begin(), (x).end() int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; constexpr int INF = 1 << 30; constexpr ll LINF = 1LL << 40; constexpr ll mod = 1e9 + 7; void flush() { cout << flush; } template <class T> vector<T> vec(int len, T elem) { return vector<T>(len, elem); } // auto dp = vec(52, vec(103, vec(103, INF))); template <class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template <class T> inline bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } template <class T> inline int popcount(T a) { return __builtin_popcountll(a); } template <class T> inline T emod(T a, T p) { return (a % p + p) % p; } template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '\n'; for (auto v : vec) os << v << ' '; os << '\n'; return os; } template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; } template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } struct MyIO { MyIO() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } IO_OI; #ifdef LOCAL void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...); } #define debug(...) \ cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif //------------------- template <class T, class E> struct SegmentTree { using F = function<T(T, T)>; using G = function<T(T, E)>; using H = function<E(E, E)>; using P = function<E(E, int)>; int n; F f; G g; // pで変換したものをdataに移す時 H h; // lazyを遷移させる時 P p; // lazyを必要な形に変換 T d1; E d0; vector<T> dat; vector<E> laz; SegmentTree( int n_, F f, G g, H h, T d1, E d0, vector<T> v = vector<T>(), P p = [](E a, int b) { return a; }) : f(f), g(g), h(h), d1(d1), d0(d0), p(p) { init(n_); if (n_ == (int)v.size()) build(n_, v); } void init(int n_) { n = 1; while (n < n_) n *= 2; dat.clear(); dat.resize(2 * n - 1, d1); laz.clear(); laz.resize(2 * n - 1, d0); } void build(int n_, vector<T> v) { for (int i = 0; i < n_; i++) dat[i + n - 1] = v[i]; for (int i = n - 2; i >= 0; i--) dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]); } inline void eval(int len, int k) { if (laz[k] == d0) return; if (k * 2 + 1 < n * 2 - 1) { laz[k * 2 + 1] = h(laz[k * 2 + 1], laz[k]); laz[k * 2 + 2] = h(laz[k * 2 + 2], laz[k]); } dat[k] = g(dat[k], p(laz[k], len)); laz[k] = d0; } T update(int a, int b, E x, int k, int l, int r) { eval(r - l, k); if (r <= a || b <= l) return dat[k]; if (a <= l && r <= b) { laz[k] = h(laz[k], x); return g(dat[k], p(laz[k], r - l)); } return dat[k] = f(update(a, b, x, k * 2 + 1, l, (l + r) / 2), update(a, b, x, k * 2 + 2, (l + r) / 2, r)); } T update(int a, int b, E x) { return update(a, b, x, 0, 0, n); } T _query(int a, int b, int k, int l, int r) { eval(r - l, k); if (r <= a || b <= l) return d1; if (a <= l && r <= b) return dat[k]; T vl = _query(a, b, k * 2 + 1, l, (l + r) / 2); T vr = _query(a, b, k * 2 + 2, (l + r) / 2, r); return f(vl, vr); } T query(int a, int b) { return _query(a, b, 0, 0, n); } }; // END CUT HERE signed main() { int n, q; cin >> n; vector<ll> a(n); cin >> a >> q; debug(a); SegmentTree<ll, ll> ch( n, [&](ll l, ll r) { return min(l, r); }, [](ll l, ll r) { return l + r; }, [](ll l, ll r) { return l + r; }, LINF, 0LL, a); while (q--) { int k, l, r; cin >> k >> l >> r; ll c; cin >> c; if (k == 1) { ch.update(l - 1, r, c); } else { cout << ch.query(l - 1, r) << endl; } } }