#293154 (C++14) No.749 クエリ全部盛り

提出ソース

結果

問題	No.749 クエリ全部盛り
ユーザー	pazzle1230
提出日時	2018-10-19 23:37:00
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	574 ms / 3,000 ms
コード長	7,611 bytes
コンパイル時間	2,115 ms
コンパイル使用メモリ	186,804 KB
実行使用メモリ	167,240 KB
最終ジャッジ日時	2023-08-12 02:32:02
合計ジャッジ時間	6,857 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	3 ms 4,384 KB
testcase_06	AC	4 ms 4,380 KB
testcase_07	AC	3 ms 4,380 KB
testcase_08	AC	3 ms 4,380 KB
testcase_09	AC	3 ms 4,380 KB
testcase_10	AC	24 ms 4,596 KB
testcase_11	AC	24 ms 4,752 KB
testcase_12	AC	24 ms 4,720 KB
testcase_13	AC	25 ms 4,616 KB
testcase_14	AC	24 ms 4,892 KB
testcase_15	AC	574 ms 167,072 KB
testcase_16	AC	524 ms 167,240 KB
testcase_17	AC	559 ms 167,180 KB
testcase_18	AC	558 ms 167,168 KB
testcase_19	AC	547 ms 167,172 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<class ValueMonoid, class OperatorMonoid, class Modifier,
	template<class...> class Container=::std::vector>
class LazySegTree{
public:
	using value_structure = ValueMonoid;
	using value_type = typename value_structure::value_type;
	using operator_structure = OperatorMonoid;
	using operator_type = typename operator_structure::value_type;
	using modifier = Modifier;
	using const_reference = const value_type &;
	using container_value_type = Container<value_type>;
	using container_operator_type = Container<operator_type>;
	using size_type = typename container_value_type::size_type;

private:
	container_value_type tree;
	container_operator_type lazy;
	size_type size_, height;

	static size_type getsize(const size_type x){
		size_type ret = 1;
		while(ret < x)
			ret <<= 1;
		return ret;
	}

	static size_type getheight(const size_type x){
		size_type ret = 0;
		while((static_cast<size_type>(1) << ret) < x){
			ret++;
		}
		return ret;
	}

	inline static value_type calc(const value_type a, const value_type b){
		return value_structure::operation(a, b);
	}

	inline static void apply(operator_type &data, const operator_type a){
		data = operator_structure::operation(data, a);
	}

	inline static value_type reflect(const value_type v, const operator_type o){
		return modifier::operation(v, o);
	}

	void push(const size_type index){
		tree[index] = reflect(tree[index], lazy[index]);
		apply(lazy[index << 1], lazy[index]);
		apply(lazy[index << 1 | 1], lazy[index]);
		lazy[index] = operator_structure::identity();
	}

	void calc_node(const size_type index){
		if(tree.size() <= (index << 1 | 1)) return;
		assert(0 < index);
		tree[index] = calc(reflect(tree[index << 1],  lazy[index << 1]),
				reflect(tree[index << 1 | 1], lazy[index << 1 | 1]));
	}

	void build(size_type index){
		while(index >>= 1){
			calc_node(index);
		}
	}

	void propagate(const size_type index){
		for(size_type shift = height; shift ; --shift){
			push(index >> shift);
		}
	}

	void rebuild(){
		for(size_type i = size_-1;i > 0;--i){
			calc_node(i);
		}
	}
public:
	LazySegTree() : size_(0), height(0), tree(), lazy(){}
	LazySegTree(const size_type size)
			: size_(size), height(getheight(size)),
				tree(size << 1, value_structure::initializer()),
				lazy(size << 1, operator_structure::identity()){
		rebuild();
	}
	template<class InputIterator>
	LazySegTree(InputIterator first, InputIterator last)
			: size_(::std::distance(first, last)){
		height = getheight(size_);
		tree = container_value_type(size_, value_structure::identity());
		lazy = container_operator_type(size_ << 1, operator_structure::identity());
		tree.insert(tree.end(), first, last);
		rebuild();
	}

	size_type size() const { return size_; }
	const_reference operator[](const size_type k){
		assert(k < size_);
		propagate(k+size_);
		tree[k+size_] = reflect(tree[k+size_], lazy[k+size_]);
		lazy[k+size_] = operator_structure::identity();
		return tree[k+size_];
	}

	value_type query(size_type l, size_type r){
		assert(l <= r);
		assert(0 <= l && l < size_);
		assert(0 <= r && r <= size_);
		value_type retl = value_structure::identity(),
							 retr = value_structure::identity();
		l += size_;
		r += size_;
		propagate(l);
		propagate(r-1);
		for(; l < r ; l >>= 1, r >>= 1){
			if(l&1){
				retl = calc(retl, reflect(tree[l], lazy[l]));
				l++;
			}
			if(r&1){
				r--;
				retr = calc(reflect(tree[r], lazy[r]), retr);
			}
		}
		return calc(retl, retr);
	}

	void update(size_type l, size_type r, const operator_type& data){
		assert(l <= r);
		assert(0 <= l && l < size_);
		assert(0 <= r && r <= size_);
		l += size_;
		r += size_;
		propagate(l);
		propagate(r - 1);
		for(size_type l_ = l, r_ = r; l_ < r_ ; l_ >>= 1, r_ >>= 1){
			if(l_ & 1) apply(lazy[l_++], data);
			if(r_ & 1) apply(lazy[--r_], data);
		}
		build(l);
		build(r - 1);
	}

	template<class F>
	void update(size_type index, const F& f){
		assert(0 <= index && index < size());
		index += size_;
		propagate(index);
		tree[index] = f(::std::move(tree[index]));
		lazy[index] = operator_structure::identity();
		build(index);
	}

	/*
	template<class F>
	size_type search(const F& f) const { // [0, result) is True and [0, result-1) is not.
		if(f(value_structure::identity()))
			return 0;
		if(!f(tree[1]))
			return size_+1;
		value_type acc = value_structure::identity();
		size_type i = 1;
		while(i < 
	}
	*/
};

const int64 mod = 1e9+7;

int64 gcd(int64 a, int64 b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

vector<int64> fib;

struct value{
	int64 v;
	int64 l, r;
	value():v(0), l(0), r(0){}
	value(int64 v_, int64 l_, int64 r_){
		v = v_; l = l_; r = r_;
	}
	const value operator+(const value& rhs) const{
		return value((v+rhs.v)%mod, l, rhs.r);
	};
};

class vmonoid{  
public:
	using value_type = value;
	static value_type identity(){return value(0, 0, 0);}
	static value_type initializer(){return value(0, 0, 0);}
	static value_type operation(const value_type& a, const value_type& b){
		return value((a.v+b.v)%mod, a.l, b.r);
	}
};

class omonoid{
public:
	using value_type = tuple<int64, int64, int64, int64>;
	static value_type identity(){return value_type(0, 1, -1, 0);}
	static value_type operation(const value_type& a, const value_type& b){
		int64 a0, a1, a2, a3, b0, b1, b2, b3;
		tie(a0, a1, a2, a3) = a;
		tie(b0, b1, b2, b3) = b;
		//printf("(%lld %lld %lld), (%lld %lld %lld), ", a0, a1, a2, b0, b1, b2);
		if(b2 > -1){
		//	printf("(%lld %lld %lld)\n", 0LL, 1LL, b2);
			return b;
		}
		//printf("(%lld %lld %lld)\n", a0*b1+b0, a1*b1, a2);
		return value_type((a0*b1%mod+b0)%mod, a1*b1%mod, a2, ((a3*b1)%mod+b3)%mod);
	}
};

class modifier{
public:
	using vl = vmonoid::value_type;
	using op = omonoid::value_type;
	static vl operation(const vl& a, const op& b){
		int64 a0, a1, a2, a3;
		tie(a0, a1, a2, a3) = b;
		if(a2 > -1){
			return value(((a2*a1%mod+a0)%mod*(a.r-a.l)%mod+((fib[a.r]-fib[a.l]+mod)%mod)*a3%mod)%mod, a.l, a.r);
		}
		return value(((a.v*a1%mod+a0*(a.r-a.l)%mod)%mod+(fib[a.r]-fib[a.l]+mod)%mod*a3%mod)%mod, a.l, a.r);
	}
};

int32 N, Q;

void init(){
	fib.resize(N+1, 0);
	fib[2] = 1;
	FOR(i, 3, N+1){
		fib[i] = fib[i-1]+fib[i-2];
		fib[i] %= mod;
	}
	FOR(i, 1, N+1){
		fib[i] += fib[i-1];
		fib[i] %= mod;
	}
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);

	scanf("%d %d", &N, &Q);
	init();
	vector<value> v(N);
	REP(i, N){
		v[i] = value(0, i, i+1);
	}

	LazySegTree<vmonoid, omonoid, modifier>
		lsg(v.begin(), v.end());
	REP(i, Q){
		int64 q, l, r, k;
		scanf("%lld %lld %lld %lld", &q, &l, &r, &k); r++;
		if(q == 0){
			printf("%lld\n", lsg.query(l, r).v*k%mod);
		}else if(q == 1){
			lsg.update(l, r, omonoid::value_type(0, 1, k, 0));
		}else if(q == 2){
			lsg.update(l, r, omonoid::value_type(k, 1, -1, 0));
		}else if(q == 3){
			lsg.update(l, r, omonoid::value_type(0, k, -1, 0));
		}else if(q == 4){
			lsg.update(l, r, omonoid::value_type(0, 1, -1, k));
		}
		/*
		REP(i, N){
			cout << lsg[i].v << " ";
		}
		cout << endl;
		*/
	}
}

yukicoder

結果

テストケース

ソースコード