Submit Info #22239

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp Mehedi AC 606 ms 39.15 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 594 ms 39.09 MiB
max_random_01 AC 585 ms 39.08 MiB
max_random_02 AC 606 ms 39.15 MiB
medium_00 AC 3 ms 0.79 MiB
medium_01 AC 4 ms 0.65 MiB
medium_02 AC 5 ms 0.70 MiB
random_00 AC 378 ms 20.30 MiB
random_01 AC 419 ms 38.50 MiB
random_02 AC 239 ms 10.59 MiB
small_00 AC 1 ms 0.57 MiB
small_01 AC 3 ms 0.62 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 1 ms 0.66 MiB
small_04 AC 3 ms 0.38 MiB
small_05 AC 1 ms 0.62 MiB
small_06 AC 2 ms 0.67 MiB
small_07 AC 1 ms 0.65 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 2 ms 0.67 MiB

#include <bits/stdc++.h> #define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i)) #define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i)) #define rep(i, n) For((i), 0, (n)) #define rrep(i, n) rFor((i), (n), 0) #define fi first #define se second using namespace std; typedef long long lint; typedef unsigned long long ulint; typedef pair<int, int> pii; typedef pair<lint, lint> pll; template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false;} template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false;} template<class T> T div_floor(T a, T b) { if (b < 0) a *= -1, b *= -1; return a >= 0 ? a / b : (a + 1) / b - 1; } template<class T> T div_ceil(T a, T b) { if (b < 0) a *= -1, b *= -1; return a > 0 ? (a - 1) / b + 1 : a / b; } template < typename F, typename S >ostream& operator << ( ostream& os, const pair< F, S > & p ) {return os << "(" << p.first << ", " << p.second << ")";} template < typename T >ostream &operator << ( ostream & os, const vector< T > &v ) {os << "{"; for (auto it = v.begin(); it != v.end(); ++it) {if ( it != v.begin() ) os << ", "; os << *it;} return os << "}";} template < typename T >ostream &operator << ( ostream & os, const set< T > &v ) {os << "["; for (auto it = v.begin(); it != v.end(); ++it) {if ( it != v.begin()) os << ", "; os << *it;} return os << "]";} template < typename F, typename S >ostream &operator << ( ostream & os, const map< F, S > &v ) {os << "["; for (auto it = v.begin(); it != v.end(); ++it) {if ( it != v.begin() ) os << ", "; os << it -> first << " = " << it -> second ;} return os << "]";} #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) clock_t tStart = clock(); #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) void faltu () { cerr << endl; } template <typename T>void faltu( T a[], int n ) {for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl;} template <typename T, typename ... hello> void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } constexpr lint mod = 1e9 + 7; constexpr lint INF = mod * mod; constexpr int MAX = 200010; struct SegTree_beats { static constexpr lint b_INF = 1LL << 60; int sz; vector<lint> MAX_val, sMAX_val, MAX_cnt; vector<lint> min_val, smin_val, min_cnt; vector<lint> len, sum, ladd, lval; void init_node(int i, lint x) { MAX_val[i] = min_val[i] = sum[i] = x; sMAX_val[i] = -b_INF; smin_val[i] = b_INF; MAX_cnt[i] = min_cnt[i] = 1; } void init_empty_node(int i) { MAX_val[i] = sMAX_val[i] = -b_INF; min_val[i] = smin_val[i] = b_INF; MAX_cnt[i] = min_cnt[i] = 0; } void update_node_max(int i, lint x) { sum[i] += (x - MAX_val[i]) * MAX_cnt[i]; if (MAX_val[i] == min_val[i]) MAX_val[i] = min_val[i] = x; else if (MAX_val[i] == smin_val[i]) MAX_val[i] = smin_val[i] = x; else MAX_val[i] = x; if (lval[i] != b_INF && x < lval[i]) lval[i] = x; } void update_node_min(int i, lint x) { sum[i] += (x - min_val[i]) * min_cnt[i]; if (min_val[i] == MAX_val[i]) min_val[i] = MAX_val[i] = x; else if (MAX_val[i] == smin_val[i]) min_val[i] = sMAX_val[i] = x; else min_val[i] = x; if (lval[i] != b_INF && lval[i] < x) lval[i] = x; } void update_node_add(int i, lint x, int l, int r) { MAX_val[i] += x; if (sMAX_val[i] != -b_INF) sMAX_val[i] += x; min_val[i] += x; if (smin_val[i] != b_INF) smin_val[i] += x; sum[i] += x * (r - l); if (lval[i] != b_INF) lval[i] += x; else ladd[i] += x; } void update_node_set(int i, lint x, int l, int r) { MAX_val[i] = min_val[i] = x; sMAX_val[i] = -b_INF; smin_val[i] = b_INF; MAX_cnt[i] = min_cnt[i] = r - l; lval[i] = x; ladd[i] = 0; } void push(int i, int l, int r) { if (lval[i] != b_INF) { update_node_set(i * 2 + 1, lval[i], l, (l + r) / 2); update_node_set(i * 2 + 2, lval[i], (l + r) / 2, r); lval[i] = INF; return; } if (ladd[i] != 0) { update_node_add(i * 2 + 1, ladd[i], l, (l + r) / 2); update_node_add(i * 2 + 2, ladd[i], (l + r) / 2, r); ladd[i] = 0; } if (MAX_val[i] < MAX_val[i * 2 + 1]) update_node_max(i * 2 + 1, MAX_val[i]); if (MAX_val[i] < MAX_val[i * 2 + 2]) update_node_max(i * 2 + 2, MAX_val[i]); if (min_val[i] > min_val[i * 2 + 1]) update_node_min(i * 2 + 1, min_val[i]); if (min_val[i] > min_val[i * 2 + 2]) update_node_min(i * 2 + 2, min_val[i]); } void pull(int i) { int s = i * 2 + 1, t = i * 2 + 2; sum[i] = sum[s] + sum[t]; if (MAX_val[s] > MAX_val[t]) { MAX_val[i] = MAX_val[s]; MAX_cnt[i] = MAX_cnt[s]; sMAX_val[i] = max(sMAX_val[s], MAX_val[t]); } else if (MAX_val[s] < MAX_val[t]) { MAX_val[i] = MAX_val[t]; MAX_cnt[i] = MAX_cnt[t]; sMAX_val[i] = max(MAX_val[s], sMAX_val[t]); } else { MAX_val[i] = MAX_val[s]; MAX_cnt[i] = MAX_cnt[s] + MAX_cnt[t]; sMAX_val[i] = max(sMAX_val[s], sMAX_val[t]); } if (min_val[s] < min_val[t]) { min_val[i] = min_val[s]; min_cnt[i] = min_cnt[s]; smin_val[i] = min(smin_val[s], min_val[t]); } else if (min_val[s] > min_val[t]) { min_val[i] = min_val[t]; min_cnt[i] = min_cnt[t]; smin_val[i] = min(min_val[s], smin_val[t]); } else { min_val[i] = min_val[s]; min_cnt[i] = min_cnt[s] + min_cnt[t]; smin_val[i] = min(smin_val[s], smin_val[t]); } } SegTree_beats(int sz_, vector<lint> &a) { sz = 1; while (sz < sz_) sz *= 2; dbg(sz); MAX_val.resize(sz * 2 - 1); sMAX_val.resize(sz * 2 - 1); MAX_cnt.resize(sz * 2 - 1); min_val.resize(sz * 2 - 1); smin_val.resize(sz * 2 - 1); min_cnt.resize(sz * 2 - 1); sum.resize(sz * 2 - 1); ladd.resize(sz * 2 - 1, 0); lval.resize(sz * 2 - 1, b_INF); rep(i, a.size()) init_node(i + sz - 1, a[i]); For(i, a.size(), sz) init_empty_node(i + sz - 1); rrep(i, sz - 1) pull(i); } void update_min(int a, int b, lint x, int i = 0, int l = 0, int r = -1) { if (r < 0) r = sz; if (r <= a || b <= l || MAX_val[i] <= x) return; else if (a <= l && r <= b && sMAX_val[i] < x) { update_node_max(i, x); } else { push(i, l, r); update_min(a, b, x, i * 2 + 1, l, (l + r) / 2); update_min(a, b, x, i * 2 + 2, (l + r) / 2, r); pull(i); } } void update_max(int a, int b, lint x, int i = 0, int l = 0, int r = -1) { if (r < 0) r = sz; if (r <= a || b <= l || min_val[i] >= x) return; else if (a <= l && r <= b && smin_val[i] > x) { update_node_min(i, x); } else { push(i, l, r); update_max(a, b, x, i * 2 + 1, l, (l + r) / 2); update_max(a, b, x, i * 2 + 2, (l + r) / 2, r); pull(i); } } void update_add(int a, int b, lint x, int i = 0, int l = 0, int r = -1) { if (r < 0) r = sz; if (r <= a || b <= l) return; else if (a <= l && r <= b) update_node_add(i, x, l, r); else { push(i, l, r); update_add(a, b, x, i * 2 + 1, l, (l + r) / 2); update_add(a, b, x, i * 2 + 2, (l + r) / 2, r); pull(i); } } void update_set(int a, int b, lint x, int i = 0, int l = 0, int r = -1) { if (r < 0) r = sz; if (r <= a || b <= l) return; else if (a <= l && r <= b) update_node_set(i, x, l, r); else { push(i, l, r); update_set(a, b, x, i * 2 + 1, l, (l + r) / 2); update_set(a, b, x, i * 2 + 2, (l + r) / 2, r); pull(i); } } lint get_sum(int a, int b, int i = 0, int l = 0, int r = -1) { if (r < 0) r = sz; if (r <= a || b <= l) return 0; else if (a <= l && r <= b) return sum[i]; push(i, l, r); lint vl = get_sum(a, b, i * 2 + 1, l, (l + r) / 2); lint vr = get_sum(a, b, i * 2 + 2, (l + r) / 2, r); return vl + vr; } }; int main() { /* #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int n, q; scanf("%d%d", &n, &q); // dbg(n, q); vector<lint> a(n); rep(i, n) scanf("%lld", &a[i]); // dbg(a); SegTree_beats st(n, a); rep(_, q) { int t, l, r; lint b; // dbg(t, l, r); scanf("%d%d%d", &t, &l, &r); if (t == 0) { scanf("%lld", &b); st.update_min(l, r, b); } else if (t == 1) { scanf("%lld", &b); st.update_max(l, r, b); } else if (t == 2) { scanf("%lld", &b); st.update_add(l, r, b); } else printf("%lld\n", st.get_sum(l, r)); } }