#386293 (C++17) No.880 Yet Another Segment Tree Problem

提出ソース

結果

問題	No.880 Yet Another Segment Tree Problem
ユーザー	sigma425
提出日時	2019-10-04 02:19:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	690 ms / 5,000 ms
コード長	4,191 bytes
コンパイル時間	4,551 ms
コンパイル使用メモリ	212,036 KB
実行使用メモリ	12,332 KB
最終ジャッジ日時	2023-10-24 02:44:12
合計ジャッジ時間	18,298 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,368 KB
testcase_01	AC	3 ms 4,368 KB
testcase_02	AC	5 ms 4,368 KB
testcase_03	AC	4 ms 4,368 KB
testcase_04	AC	4 ms 4,368 KB
testcase_05	AC	3 ms 4,368 KB
testcase_06	AC	3 ms 4,368 KB
testcase_07	AC	4 ms 4,368 KB
testcase_08	AC	4 ms 4,368 KB
testcase_09	AC	5 ms 4,368 KB
testcase_10	AC	4 ms 4,368 KB
testcase_11	AC	636 ms 12,068 KB
testcase_12	AC	624 ms 12,068 KB
testcase_13	AC	444 ms 12,068 KB
testcase_14	AC	618 ms 12,332 KB
testcase_15	AC	656 ms 12,332 KB
testcase_16	AC	688 ms 12,332 KB
testcase_17	AC	637 ms 12,332 KB
testcase_18	AC	652 ms 12,332 KB
testcase_19	AC	327 ms 12,332 KB
testcase_20	AC	339 ms 12,332 KB
testcase_21	AC	343 ms 12,332 KB
testcase_22	AC	334 ms 12,332 KB
testcase_23	AC	342 ms 12,332 KB
testcase_24	AC	299 ms 12,332 KB
testcase_25	AC	311 ms 12,332 KB
testcase_26	AC	318 ms 12,332 KB
testcase_27	AC	304 ms 12,332 KB
testcase_28	AC	316 ms 12,332 KB
testcase_29	AC	605 ms 12,332 KB
testcase_30	AC	650 ms 12,332 KB
testcase_31	AC	690 ms 12,332 KB
testcase_32	AC	168 ms 12,332 KB
testcase_33	AC	293 ms 12,332 KB
testcase_34	AC	311 ms 12,332 KB
testcase_35	AC	295 ms 12,332 KB
testcase_36	AC	295 ms 12,332 KB
testcase_37	AC	301 ms 12,332 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
		}

	}
}

yukicoder

結果

テストケース

ソースコード