結果

問題 No.1234 典型RMQ
ユーザー hamamuhamamu
提出日時 2020-09-18 22:24:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 144 ms / 2,000 ms
コード長 6,495 bytes
コンパイル時間 2,620 ms
コンパイル使用メモリ 213,708 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-11-09 01:58:00
合計ジャッジ時間 6,922 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 130 ms
7,936 KB
testcase_07 AC 96 ms
5,248 KB
testcase_08 AC 144 ms
8,064 KB
testcase_09 AC 118 ms
5,504 KB
testcase_10 AC 138 ms
8,064 KB
testcase_11 AC 130 ms
7,808 KB
testcase_12 AC 114 ms
5,632 KB
testcase_13 AC 97 ms
5,248 KB
testcase_14 AC 117 ms
5,632 KB
testcase_15 AC 113 ms
5,504 KB
testcase_16 AC 137 ms
7,936 KB
testcase_17 AC 114 ms
5,632 KB
testcase_18 AC 86 ms
5,248 KB
testcase_19 AC 136 ms
8,064 KB
testcase_20 AC 79 ms
8,064 KB
testcase_21 AC 132 ms
7,936 KB
testcase_22 AC 101 ms
8,064 KB
testcase_23 AC 102 ms
8,064 KB
testcase_24 AC 101 ms
8,192 KB
testcase_25 AC 102 ms
8,064 KB
testcase_26 AC 101 ms
7,936 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
using     ll=long long;
using    vll=vector<   ll>;
using   vvll=vector<  vll>;
using  vvvll=vector< vvll>;
using vvvvll=vector<vvvll>;
constexpr ll INF = 1LL << 60;
struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(numeric_limits<double>::max_digits10); } } fast;
#define REPS(i, S, E) for (ll i = (S); i <= (E); i++)
#define REP(i, N) REPS(i, 0, (N)-1)
#define DEPS(i, S, E) for (ll i = (E); i >= (S); i--)
#define DEP(i, N) DEPS(i, 0, (N)-1)
#define rep(i, S, E)  for (ll i = (S); i <= (E); i++)
#define dep(i, E, S)  for (ll i = (E); i >= (S); i--)
#define each(e, v) for (auto&& e : v)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
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; }
template<class T> inline T MaxE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmax(m,v[i]); return m; }
template<class T> inline T MinE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmin(m,v[i]); return m; }
template<class T> inline T MaxE(vector<T> &v) { return MaxE(v,0,(ll)v.size()-1); }
template<class T> inline T MinE(vector<T> &v) { return MinE(v,0,(ll)v.size()-1); }
template<class T> inline T Sum(vector<T> &v,ll S,ll E){ T s=T(); rep(i,S,E)s+=v[i]; return s; }
template<class T> inline T Sum(vector<T> &v) { return Sum(v,0,v.size()-1); }
template<class T> inline ll sz(T &v){ return (ll)v.size(); }
inline ll CEIL(ll a,ll b){ return (a<0) ? -(-a/b) : (a+b-1)/b; }
inline ll FLOOR(ll a,ll b){ return -CEIL(-a,b); }


#if 0
#include <atcoder/all>
using namespace atcoder;
#endif

template <class T, class E> struct LazySegmentTree{
	using F = function<T(T, T)>;
	using G = function<T(T, E)>;
	using H = function<E(E, E)>;
	F f; //!< データ同士の合成関数
	G g; //!< 作用関数
	H h; //!< 作用素同士の合成関数
	T ti; //!< データの単位元 実際の単位元をセットしないとだめ
	E ei; //!< 作用素の単位元 実際の単位元ではなくても、使わない値ならOK
	ll n=1; //!< データ数の2べき上界
	vector<T> dat;
	vector<E> laz;
	LazySegmentTree() {}
	LazySegmentTree(vector<T> &v, F f, G g, H h, T ti, E ei) { Init(v, f, g, h, ti, ei); }
	void Init(vector<T> &v, F f, G g, H h, T ti, E ei){
		this->f=f; this->g=g; this->h=h; this->ti=ti; this->ei=ei;
		while (n<(ll)v.size()) n<<=1;
		dat.resize(2*n-1, ti);
		laz.resize(2*n-1, ei);
		for (ll i=0; i<(ll)v.size(); i++) dat[n-1+i] = v[i];
		for (ll i=n-2; i>=0; i--) dat[i] = f(dat[2*i+1], dat[2*i+2]);
	}
	void Update(ll a, ll b, E x){ update(a, b+1, x, 0, 0, n); } //[a,b]にxを作用
	void update(ll a, ll b, E x, ll k, ll l, ll r){ //注目ノードk=[l,r)
		if (r<=a || b<=l) eval(k); //[l,r)が[a,b)と重ならない時
		else if (a<=l && r<=b){ //[l,r)が[a,b)の内側の時
			laz[k] = h(laz[k], x);
			eval(k); //親ノードが後でdat[k]を見るため、ここで評価しておく必要あり
		}
		else { //[l,r)が[a,b)から一部はみ出す時
			eval(k); //子ノードを処理する前に評価しておく必要あり
			update(a, b, x, k*2+1, l, (l+r)/2);
			update(a, b, x, k*2+2, (l+r)/2, r);
			dat[k] = f(dat[k*2+1], dat[k*2+2]);
		}
	}
	T Range(ll a, ll b) { return range(a, b+1, 0, 0, n); }//[a,b]の値を取得
	T range(ll a, ll b, ll k, ll l, ll r){ //注目ノードk=[l,r)
		if (r<=a || b<=l) return ti; //[l,r)が[a,b)と重ならない時
		eval(k); //自分や子の値を見る前に評価が必要
		if (a<=l && r<=b) return dat[k];//[l,r)が[a,b)の内側の時
		return f(range(a, b, k*2+1, l, (l+r)/2), range(a, b, k*2+2, (l+r)/2, r));
		//[l,r)が[a,b)から一部はみ出す時
	}
	ll FindL(ll a, ll b, T x) { return findL(a, b+1, x, 0, 0, n); }
	ll findL(ll a, ll b, T x, ll k, ll l, ll r){ //[l,r)内最左 なければb
		if (r<=a || b<=l) return b; //範囲外
		eval(k);
		if (f(dat[k], x) != dat[k]) return b; //条件を満たさない
		if (n-1 <= k) return k-(n-1); //葉なら見つかった→位置return
		ll        i = findL(a, b, x, 2*k+1, l, (l+r)/2); //左部分木探す
		if (i==b) i = findL(a, b, x, 2*k+2, (l+r)/2, r); //左になければ右
		return i;
	}
	ll FindR(ll a, ll b, T x) { return findR(a, b+1, x, 0, 0, n); }
	ll findR(ll a, ll b, T x, ll k, ll l, ll r){ //[l,r)内最右 なければa-1
		if (r<=a || b<=l) return a-1; //範囲外
		eval(k);
		if (f(dat[k], x) != dat[k]) return a-1; //条件を満たさない
		if (n-1 <= k) return k-(n-1); //葉なら見つかった→位置return
		ll          i = findR(a, b, x, 2*k+2, (l+r)/2, r); //右部分木探す
		if (i==a-1) i = findR(a, b, x, 2*k+1, l, (l+r)/2); //右になければ左
		return i;
	}
	void eval(ll k){
		if (laz[k] == ei) return;
		if (k<=n-2){ //子に作用素を配る
			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], laz[k]);
		laz[k] = ei;
	}
	void Dump(ll w=5){
		auto disp=[&](ll x){
			if (x==-INF) cerr << setw(w) << "-INF";
			else if (x== INF) cerr << setw(w) << "INF";
			else              cerr << setw(w) << x;
		};
		REP(i, n) for (ll k=i+n-1, m=1, p=1; k>=0; p=m, m*=k%2, k=(k==0)?-1:(k-1)/2){
			if (m){
				cerr << ((k<n-1)?" ┬ ":""); disp(dat[k]); cerr<<" /"; disp(laz[k]);
			}
			else{
				cerr << ((p&~m) ?" ┘ ":"");
			}
			if (k==0) cerr << '\n';
		} cerr << '\n';
	}
};


void solve()
{
	ll n;  cin >> n;
	vector<ll> a(n);  rep(i,0,n-1){ ll a_; cin>>a_; a[i]=a_; }


	LazySegmentTree<ll, ll> sgt(
		a,
		[](ll x, ll y){ return min(x, y); },//データ同士の合成関数
		[](ll x, ll y){ return x + y; },//データxに作用素yを作用させる関数
		[](ll x, ll y){ return x + y; },//作用素の合成関数
		INF, //データの単位元 実際の単位元をセットしないとだめ
		0); //作用素の単位元 実際の単位元ではなくても、使わない値ならOK

	ll q;  cin >> q;
	rep(qq,0,q-1){
		ll k,l,r,c;  cin >> k >> l >> r >> c;
		l--;r--;
		if (k==1){
			sgt.Update(l, r, c);
		}
		else{//k=2
			ll ans=sgt.Range(l, r);
			cout << ans << '\n';
		}
	}
}


int main(){
#if 1
	solve();
#else
	ll t;  cin >> t;
	rep(i, 0, t-1){
		solve();
	}
#endif
	return 0;
}
0