結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー sigma425sigma425
提出日時 2019-10-04 02:19:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 696 ms / 5,000 ms
コード長 4,191 bytes
コンパイル時間 2,389 ms
コンパイル使用メモリ 212,516 KB
実行使用メモリ 12,296 KB
最終ジャッジ日時 2024-09-22 19:40:53
合計ジャッジ時間 16,413 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 4 ms
5,376 KB
testcase_02 AC 5 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 641 ms
12,160 KB
testcase_12 AC 629 ms
12,124 KB
testcase_13 AC 444 ms
11,956 KB
testcase_14 AC 619 ms
12,176 KB
testcase_15 AC 661 ms
12,128 KB
testcase_16 AC 690 ms
12,236 KB
testcase_17 AC 639 ms
12,232 KB
testcase_18 AC 655 ms
12,284 KB
testcase_19 AC 337 ms
12,112 KB
testcase_20 AC 338 ms
12,184 KB
testcase_21 AC 345 ms
12,144 KB
testcase_22 AC 336 ms
12,132 KB
testcase_23 AC 348 ms
12,072 KB
testcase_24 AC 304 ms
12,220 KB
testcase_25 AC 324 ms
12,276 KB
testcase_26 AC 319 ms
12,080 KB
testcase_27 AC 311 ms
12,200 KB
testcase_28 AC 331 ms
12,076 KB
testcase_29 AC 613 ms
12,172 KB
testcase_30 AC 653 ms
12,180 KB
testcase_31 AC 696 ms
12,196 KB
testcase_32 AC 169 ms
12,296 KB
testcase_33 AC 298 ms
12,152 KB
testcase_34 AC 316 ms
12,196 KB
testcase_35 AC 302 ms
12,056 KB
testcase_36 AC 296 ms
12,200 KB
testcase_37 AC 300 ms
12,216 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

template<class N>
struct segbeats{
	V<N> x;
	int s;
	template<class T>
	segbeats(const V<T>& a){
		int n = a.size();
		s = 1;
		while(s<n) s *= 2;
		x.resize(s*2);
		rep(i,n) x[s+i] = N(a[i]);
		for(int i=s-1;i>0;i--) upd(i);
	}

	template<class F,class... Args>
	void ch(int a,int b,F f,Args... args){
		ch_(a,b,0,s,1,f,args...);
	}

	template<class F,class G,class H>
	auto get(int a,int b,F f,G g,H h){
		return get_(a,b,0,s,1,f,g,h);
	}

	template<class F,class... Args>
	pair<int,N> findl(int a,int b,F f,Args&... args){
		return findl_(a,b,0,s,1,f,args...);
	}

	private:

	void push(int i){
		x[i].push(x[i*2],x[i*2+1]);
	}
	void upd(int i){
		x[i] = N::merge(x[i*2],x[i*2+1]);
	}

	template<class F,class... Args>
	void ch_(int a,int b,int l,int r,int i,F f,Args... args){
		if(b<=l || r<=a){
			return;
		}
		if(a<=l && r<=b && (x[i].*f)(args...)){    //f : put_tag, early_break
			return;
		}
		push(i);
		int m = (l+r)/2;
		ch_(a,b,l,m,i*2  ,f,args...);
		ch_(a,b,m,r,i*2+1,f,args...);
		upd(i);
	}
	template<class F,class G,class H>
	auto get_(int a,int b,int l,int r,int i,F f,G g,H h){
		if(b<=l || r<=a){
			return h;
		}
		if(a<=l && r<=b){
			return (x[i].*f)();
		}
		push(i);
		int m = (l+r)/2;
		return g(get_(a,b,l,m,i*2,f,g,h),get_(a,b,m,r,i*2+1,f,g,h));
	}
	template<class F,class... Args>
	pair<int,N> findl_(int a,int b,int l,int r,int i,F f,Args&... args){
		if(b<=l || r<=a){
			return {b,N()};
		}
		if(a<=l && r<=b){
			if(!(x[i].*f)(args...)) return {b,N()};
			if(r-l == 1) return {l,x[i]};
		}
		push(i);
		int m = (l+r)/2;
		auto x = findl_(a,b,l,m,i*2,f,args...);
		if(x.fs < b) return x;
		return findl_(a,b,m,r,i*2+1,f,args...);
	}

	// template<class F,class... Args>
	// pair<int,N> findr_(int a,int b,int l,int r,int i,F f,Args&... args){
	// 	if(b<=l || r<=a){
	// 		return {a-1,N()};
	// 	}
	// 	if(a<=l && r<=b){
	// 		if(!(x[i].*f)(args...)) return {a-1,N()};
	// 		if(r-l == 1) return {l,x[i]};
	// 	}
	// 	push(i);
	// 	int m = (l+r)/2;
	// 	auto y = findr_(a,b,m,r,i*2+1,f,args...);
	// 	if(y.fs >= a) return y;
	// 	return findr_(a,b,l,m,i*2,f,args...);
	// }
	
};

const ll inf = TEN(9)+1;
ll lcm(ll x,ll y){
	return min(x / __gcd(x,y) * y, inf);
}

struct D{
	int sz=1;
	ll sm=0,mx=-1;
	ll L=0;
	D(ll v=1){sm=mx=L=v;}
	static D merge(D l,D r){
		D z;
		z.sz = l.sz + r.sz;
		z.sm = l.sm + r.sm;
		z.mx = max(l.mx,r.mx);
		z.L = lcm(l.L,r.L);
		return z;
	}
	void push(D& x,D& y){
		if(mx * sz == sm){
			x.set(mx);
			y.set(mx);
		}
	}
	bool set(ll x){
		sm = x * sz;
		mx = L = x;
		return true;
	}
	bool gcd(ll x){
		if(x % L == 0) return true;	// break_condition
		if(mx * sz == sm){		// put_tag_condition
			set(__gcd(mx,x));
			return true;
		}
		return false;
	}
	ll getmax(){
		return mx;
	}
	ll getsum(){
		return sm;
	}
};

int main(){
	int N,Q;
	cin >> N >> Q;
	V<ll> a(N); rep(i,N) cin >> a[i];
	segbeats<D> seg(a);

	rep(_,Q){
		int t;
		cin >> t;
		if(t == 1){
			int l,r,x;
			cin >> l >> r >> x; l--;
			seg.ch(l,r,&D::set,x);
		}
		if(t == 2){
			int l,r,x;
			cin >> l >> r >> x; l--;
			seg.ch(l,r,&D::gcd,x);
		}
		if(t == 3){
			int l,r;
			cin >> l >> r; l--;
			cout << seg.get(l,r,&D::getmax,[](ll x,ll y){return max(x,y);},-1LL) << endl;
		}
		if(t == 4){
			int l,r;
			cin >> l >> r; l--;
			cout << seg.get(l,r,&D::getsum,[](ll x,ll y){return x+y;},0LL) << endl;
		}

	}
}
0