Submit Info #22577

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp Thistle AC 763 ms 69.88 MiB

ケース詳細
Name Status Time Memory
example_00 AC 19 ms 31.25 MiB
max_random_00 AC 757 ms 69.88 MiB
max_random_01 AC 763 ms 69.88 MiB
max_random_02 AC 751 ms 69.83 MiB
medium_00 AC 22 ms 31.32 MiB
medium_01 AC 21 ms 31.30 MiB
medium_02 AC 23 ms 31.03 MiB
random_00 AC 498 ms 51.04 MiB
random_01 AC 535 ms 69.28 MiB
random_02 AC 347 ms 41.29 MiB
small_00 AC 21 ms 31.17 MiB
small_01 AC 20 ms 31.23 MiB
small_02 AC 22 ms 31.17 MiB
small_03 AC 22 ms 31.24 MiB
small_04 AC 19 ms 31.16 MiB
small_05 AC 21 ms 31.18 MiB
small_06 AC 21 ms 31.15 MiB
small_07 AC 22 ms 31.17 MiB
small_08 AC 23 ms 31.25 MiB
small_09 AC 21 ms 31.18 MiB

#pragma GCC target ("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define _USE_MATH_DEFINES #include<iostream> #include<string> #include<queue> #include<cmath> #include<map> #include<set> #include<list> #include<iomanip> #include<vector> #include<random> #include<functional> #include<algorithm> #include<stack> #include<cstdio> #include<cstring> #include<bitset> #include<unordered_map> #include<climits> #include<fstream> #include<complex> #include<time.h> #include<cassert> #include<functional> #include<numeric> #include<tuple> using namespace std; using ll = long long; using ld = long double; using H = pair<ll, ll>; using P = pair<ll, H>; using vi = vector<ll>; #define all(a) (a).begin(),(a).end() #define fs first #define sc second #define xx first #define yy second.first #define zz second.second #define Q(i,j,k) mkp(i,mkp(j,k)) #define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++) #define rep(i,n) rng(i, 0, (n)) #define mkp make_pair #define vec vector #define pb emplace_back #define siz(a) (int)(a).size() #define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end()) #define getidx(b,i) (lower_bound(all(b),(i))-(b).begin()) #define ssp(i,n) (i==(ll)(n)-1?"\n":" ") #define ctoi(c) (int)(c-'0') #define itoc(c) (char)(c+'0') #define cyes printf("Yes\n") #define cno printf("No\n") #define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--) #define gcj printf("Case #%lld: ",qq123_+1) #define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read() #define found(a,x) (a.find(x)!=a.end()) constexpr ll mod = (ll)1e9 + 7; constexpr ll Mod = 998244353; constexpr ld EPS = 1e-10; constexpr ll inf = (ll)3 * 1e18; constexpr int Inf = (ll)15 * 1e8; constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 }; template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } ll read() { ll u, k = scanf("%lld", &u); return u; } string reads() { string s; cin >> s; return s; } H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; } bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; } bool ina(int t, int l, int r) { return l <= t && t < r; } ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; } ll popcount(ll x) { int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++; return sum; } template<typename T> class csum { vec<T> v; public: csum(vec<T>& a) :v(a) { build(); } csum() {} void init(vec<T>& a) { v = a; build(); } void build() { for (int i = 1; i < v.size(); i++) v[i] += v[i - 1]; } //[l,r] T a(int l, int r) { if (r < l) return 0; return v[r] - (l == 0 ? 0 : v[l - 1]); } //[l,r) T b(int l, int r) { return a(l, r - 1); } T a(pair<int, int>t) { return a(t.first, t.second); } T b(pair<int, int>t) { return b(t.first, t.second); } }; class mint { public:ll v; mint(ll v = 0) { s(v % mod + mod); } constexpr static int mod = (ll)1e9 + 7; constexpr static int fn_ = (ll)2e6 + 5; static mint fact[fn_], comp[fn_]; mint pow(int x) const { mint b(v), c(1); while (x) { if (x & 1) c *= b; b *= b; x >>= 1; } return c; } inline mint& s(int vv) { v = vv < mod ? vv : vv - mod; return *this; } inline mint inv()const { return pow(mod - 2); } inline mint operator-()const { return mint() - *this; } inline mint& operator+=(const mint b) { return s(v + b.v); } inline mint& operator-=(const mint b) { return s(v + mod - b.v); } inline mint& operator*=(const mint b) { v = v * b.v % mod; return *this; } inline mint& operator/=(const mint b) { v = v * b.inv().v % mod; return *this; } inline mint operator+(const mint b) const { return mint(v) += b; } inline mint operator-(const mint b) const { return mint(v) -= b; } inline mint operator*(const mint b) const { return mint(v) *= b; } inline mint operator/(const mint b) const { return mint(v) /= b; } friend ostream& operator<<(ostream& os, const mint& m) { return os << m.v; } friend istream& operator>>(istream& is, mint& m) { int x; is >> x; m = mint(x); return is; } bool operator<(const mint& r)const { return v < r.v; } bool operator>(const mint& r)const { return v > r.v; } bool operator<=(const mint& r)const { return v <= r.v; } bool operator>=(const mint& r)const { return v >= r.v; } bool operator==(const mint& r)const { return v == r.v; } bool operator!=(const mint& r)const { return v != r.v; } explicit operator bool()const { return v; } explicit operator int()const { return v; } mint comb(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { if (k > * this - k) k = *this - k; mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp * comp[k.v]; } return fact[v] * comp[k.v] * comp[v - k.v]; }//nCk mint perm(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp; } return fact[v] * comp[v - k.v]; }//nPk static void combinit() { fact[0] = 1; for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * mint(i); comp[fn_ - 1] = fact[fn_ - 1].inv(); for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * mint(i + 1); } }; mint mint::fact[fn_], mint::comp[fn_]; //-------------------------------------------------------------- //-------------------------------------------------------------- class SegtreeBeats { using ll = long long; int n, rr; vector<ll>mx_v, mn_v, smx_v, smn_v, lz_upd, lz_ad, sigm, len; vector<int>mx_c, mn_c; const ll mx = 1e18, mn = -1e18; public: SegtreeBeats() {} SegtreeBeats(vector<ll>& v) { init(v); } void init(vector<ll>& v) { n = v.size(); rr = 1; while (rr < n) rr *= 2; mx_v.assign(2 * rr - 1, mn); mn_v.assign(2 * rr - 1, mx); smx_v.assign(2 * rr - 1, mn); smn_v.assign(2 * rr - 1, mx); lz_upd.assign(2 * rr - 1, mx); lz_ad.assign(2 * rr - 1, 0); len.assign(2 * rr - 1, rr); sigm.assign(2 * rr - 1, 0); mx_c.assign(2 * rr - 1, 1); mn_c.assign(2 * rr - 1, 1); for (int i = 0; i < rr - 1; i++) len[i * 2 + 1] = len[i * 2 + 2] = len[i] >> 1; for (int i = 0; i < n; i++) { mx_v[i + rr - 1] = mn_v[i + rr - 1] = sigm[i + rr - 1] = v[i]; mx_c[i + rr - 1] = mn_c[i + rr - 1] = 1; } for (int i = rr - 2; i >= 0; i--) { proc(i); } } void chmin(int a, int b,ll x) { chmin(0, a, b, 0, rr,x); } void chmax(int a, int b,ll x) { chmax(0, a, b, 0, rr,x); } void update(int a, int b,ll x) { update(0, a, b, 0, rr, x); } void add(int a, int b, ll x) { add(0, a, b, 0, rr, x); } ll rangemin(int a, int b) { return rangemin(0, a, b, 0, rr); } ll rangemax(int a, int b) { return rangemax(0, a, b, 0, rr); } ll sum(int a, int b) { return sum(0, a, b, 0, rr); } private: ll rangemin(int i, int a, int b, int l, int r) { if (r <= a || b <= l) return mx; if (a <= l && r <= b) return mn_v[i]; eval(i); ll lv = rangemin(i * 2 + 1, a, b, l, (l + r) / 2); ll rv = rangemin(i * 2 + 2, a, b, (l + r) / 2,r); return min(lv, rv); } ll rangemax(int i, int a, int b, int l, int r) { if (r <= a || b <= l) return mn; if (a <= l && r <= b) return mx_v[i]; eval(i); ll lv = rangemax(i * 2 + 1, a, b, l, (l + r) / 2); ll rv = rangemax(i * 2 + 2, a, b, (l + r) / 2, r); return max(lv, rv); } ll sum(int i, int a, int b, int l, int r) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return sigm[i]; eval(i); ll lv = sum(i * 2 + 1, a, b, l, (l + r) / 2); ll rv = sum(i * 2 + 2, a, b, (l + r) / 2, r); return lv + rv; } void chmin(int i, int a, int b, int l, int r, ll x) { if (b <= l || r <= a || x >= mx_v[i]) return; if (a <= l && r <= b && smx_v[i] < x) { in_chmin(i, x); return; }//ここの値を直す。だけ。 eval(i);//子供の値も正しくする chmin(i * 2 + 1, a, b, l, (l + r) / 2, x); chmin(i * 2 + 2, a, b, (l + r) / 2, r, x); proc(i); } void chmax(int i, int a, int b, int l, int r, ll x) { if (b <= l || r <= a || x <= mn_v[i]) return; if (a <= l && r <= b && smn_v[i] > x) { in_chmax(i, x); return; }//ここの値を直す。だけ。 eval(i);//子供の値も正しくする chmax(i * 2 + 1, a, b, l, (l + r) / 2, x); chmax(i * 2 + 2, a, b, (l + r) / 2, r, x); proc(i); } void add(int i, int a, int b, int l, int r, ll x) { if (b <= l || r <= a) return; if (a <= l && r <= b) { in_add(i, x); return; }//ここの値を直す。だけ。 eval(i);//子供の値も正しくする add(i * 2 + 1, a, b, l, (l + r) / 2, x); add(i * 2 + 2, a, b, (l + r) / 2, r, x); proc(i); } void update(int i, int a, int b, int l, int r, ll x) { if (b <= l || r <= a) return; if (a <= l && r <= b) { in_update(i, x); return; }//ここの値を直す。だけ。 eval(i);//子供の値も正しくする update(i * 2 + 1, a, b, l, (l + r) / 2, x); update(i * 2 + 2, a, b, (l + r) / 2, r, x); proc(i); } void eval(int i) { //chmin, update, add //update->add 組み込む //add->chmin やるだけ //chmin->add if (i >= rr - 1) return; if (lz_upd[i] != mx) { in_update(i * 2 + 1, lz_upd[i]); in_update(i * 2 + 2, lz_upd[i]); lz_upd[i] = mx; return; }//updateされていた場合は、死ぬ if (lz_ad[i]) { in_add(i * 2 + 1, lz_ad[i]); in_add(i * 2 + 2, lz_ad[i]); lz_ad[i] = 0; } if (mx_v[i] < mx_v[i * 2 + 1]) in_chmin(i * 2 + 1, mx_v[i]); if (mx_v[i] < mx_v[i * 2 + 2]) in_chmin(i * 2 + 2, mx_v[i]); if (mn_v[i] > mn_v[i * 2 + 1]) in_chmax(i * 2 + 1, mn_v[i]); if (mn_v[i] > mn_v[i * 2 + 2]) in_chmax(i * 2 + 2, mn_v[i]); }//子供に情報を伝搬する void proc(int i) { if (i >= rr - 1) return; sigm[i] = sigm[i * 2 + 1] + sigm[i * 2 + 2]; mx_v[i] = max(mx_v[i * 2 + 1], mx_v[i * 2 + 2]); if (mx_v[i * 2 + 1] > mx_v[i * 2 + 2]) { mx_c[i] = mx_c[i * 2 + 1]; smx_v[i] = max(smx_v[i * 2 + 1], mx_v[i * 2 + 2]); } else if (mx_v[i * 2 + 1] < mx_v[i * 2 + 2]) { mx_c[i] = mx_c[i * 2 + 2]; smx_v[i] = max(smx_v[i * 2 + 2], mx_v[i * 2 + 1]); } else { mx_c[i] = mx_c[i * 2 + 1] + mx_c[i * 2 + 2]; smx_v[i] = max(smx_v[i * 2 + 1], smx_v[i * 2 + 2]); } mn_v[i] = min(mn_v[i * 2 + 1], mn_v[i * 2 + 2]); if (mn_v[i * 2 + 1] < mn_v[i * 2 + 2]) { mn_c[i] = mn_c[i * 2 + 1]; smn_v[i] = min(smn_v[i * 2 + 1], mn_v[i * 2 + 2]); } else if (mn_v[i * 2 + 1] > mn_v[i * 2 + 2]) { mn_c[i] = mn_c[i * 2 + 2]; smn_v[i] = min(smn_v[i * 2 + 2], mn_v[i * 2 + 1]); } else { mn_c[i] = mn_c[i * 2 + 1] + mn_c[i * 2 + 2]; smn_v[i] = min(smn_v[i * 2 + 1], smn_v[i * 2 + 2]); } }//子供から値を伝搬する void in_update(int i, ll x) { mx_v[i] = mn_v[i] = x; smx_v[i] = mn; smn_v[i] = mx; mx_c[i] = mn_c[i] = len[i]; sigm[i] = len[i] * x; lz_upd[i] = x, lz_ad[i] = 0; } void in_add(int i, ll x) { mx_v[i] += x; mn_v[i] += x; if (smn_v[i] != mx) smn_v[i] += x; if (smx_v[i] != mn) smx_v[i] += x; sigm[i] += x * len[i]; if (lz_upd[i] != mx) lz_upd[i] += x; lz_ad[i] += x; } void in_chmin(int i, ll x) { sigm[i] += (x - mx_v[i]) * mx_c[i]; if (mx_v[i] == mn_v[i]) mx_v[i] = mn_v[i] = x; else if (mx_v[i] == smn_v[i]) mx_v[i] = smn_v[i] = x; else mx_v[i] = x; if (lz_upd[i] != mx && lz_upd[i] > x) lz_upd[i] = x; } void in_chmax(int i, ll x) { sigm[i] += (x - mn_v[i]) * mn_c[i]; if (mn_v[i] == mx_v[i]) mx_v[i] = mn_v[i] = x; else if (mn_v[i] == smx_v[i]) mn_v[i] = smx_v[i] = x; else mn_v[i] = x; if (lz_upd[i] != mx && lz_upd[i] < x) lz_upd[i] = x; } }; int n, q; vi a; vec<pair<H, H>>qry; mt19937 rnd; void generate() { a.clear(); qry.clear(); n = rnd() % 10 + 1; q = rnd() % 20 + 1; rep(i, n) a.pb((int)(rnd() % 10) - 5); rep(i, q) { int t = rnd() % 4; int l = rnd() % n; int sz = rnd() % (n - l) + 1; if (t <= 2) { int k = (int)(rnd() % 10) - 5; qry.pb(mkp(H{ t,l }, H{ l + sz,k })); } else qry.pb(mkp(H{ t,l }, H{ l + sz,0 })); } } void guchoku() { vi b = a; for (int i = 0; i < q; i++) { int sum = 0; for (int j = qry[i].fs.sc; j < qry[i].sc.fs; j++) { if (qry[i].fs.fs == 0) { chmin(b[j], qry[i].sc.sc); } else if (qry[i].fs.fs == 1) { chmax(b[j], qry[i].sc.sc); } else if (qry[i].fs.fs == 2) { b[j] += qry[i].sc.sc; } else { sum += b[j]; } } if (qry[i].fs.fs == 3) cout << sum << endl; } cout << endl << endl; } signed main() { cin >> n >> q; rep(i, n) a.pb(read()); /* rep(i, 100) { generate(); cout << n << " " << q << endl; rep(i, n) cout << a[i] << ssp(i, n); rep(i, q) cout << qry[i].fs.fs << " " << qry[i].fs.sc << " " << qry[i].sc.fs << " " << qry[i].sc.sc << endl; cout << endl << endl; guchoku();*/ SegtreeBeats seg(a); rep(i, q) { int t; cin >> t; int l, r;ll b; cin >> l >> r; if (t == 0) { cin >> b; seg.chmin(l, r, b); } else if (t == 1) { cin >> b; seg.chmax(l, r, b); } else if (t == 2) { cin >> b; seg.add(l, r, b); } else { cout << seg.sum(l, r) << endl; } } }