Submission #1105570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105570		SamNguyen	Progression (NOI20_progression)	C++14	100 / 100	902 ms	144608 KiB

Progression

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

template <class T, class F, int N>
class SegmentTree_ {
private:
	int n;
	T st[4 * N];
	F lz[4 * N];

	void push_down(int id) {
		for (int j : {0, 1}) {
			st[id << 1 | j] += lz[id];
			lz[id << 1 | j] += lz[id];
		}
		lz[id] = F::ZERO();
	}
	
	void build(int id, int l, int r, int64_t arr[]) {
		lz[id] = F::ZERO();
		if (l == r) {
			st[id] = T(arr[l], l);
			return;
		}

		int m = (l + r) >> 1;
		build(id << 1, l, m, arr);
		build(id << 1 | 1, m + 1, r, arr);
		st[id] = st[id << 1] + st[id << 1 | 1];
	}
	
	void update(int id, int l, int r, int left, int right, F f) {
		if (r < left or right < l)
			return;

		if (left <= l and r <= right) {
			st[id] += f;
			lz[id] += f;
			return;
		}

		push_down(id);
		int m = (l + r) >> 1;
		update(id << 1, l, m, left, right, f);
		update(id << 1 | 1, m + 1, r, left, right, f);
		st[id] = st[id << 1] + st[id << 1 | 1];
	}

	T get(int id, int l, int r, int left, int right) {
		if (r < left or right < l)
			return T::ZERO();

		if (left <= l and r <= right)
			return st[id];

		push_down(id);
		int m = (l + r) >> 1;
		return get(id << 1, l, m, left, right) + get(id << 1 | 1, m + 1, r, left, right);
	}

public:
	void init(int _n, int64_t arr[]) {
		n = _n;
		build(1, 1, n, arr);
	}

	void update(int left, int right, F f) { update(1, 1, n, left, right, f); }
	T get(int left, int right) { return get(1, 1, n, left, right); }
};

struct F_ {
	bool _is_set;
	int64_t da, db;

	F_(bool __is_set = false, int64_t _da = 0, int64_t _db = 0) {
		_is_set = __is_set;
		da = _da, db = _db;
	}

	inline bool is_set() { return _is_set; }
	inline bool is_add() { return not _is_set; }

	static F_ ADD(int64_t da, int64_t db)    { return F_(false, da, db); }
	static F_ UPDATE(int64_t da, int64_t db) { return F_(true,  da, db); }
	static F_ ZERO() { return F_(); }

	F_ operator + (const F_& oth) const {
		if (oth._is_set) return oth;
		return F_(_is_set, da + oth.da, db + oth.db);
	}
	void operator += (const F_& oth) { (*this) = (*this) + oth; }
};

struct T_ {
	// y = a * i + b
	int64_t sum_i = 0, sum_a = 0, sum_b = 0, sum_ai = 0;
	int left_i, right_i;

	int64_t val_first = 0, val_last = 0;
	int64_t diff_first = 0, diff_last = 0;
	int best_len_prefix = 0, best_len_suffix = 0, best_len = 0;
	
	T_(int64_t val = 0, int64_t i = 0) {
		left_i = right_i = i;
		sum_i = i;
		sum_a = 0;
		sum_b = val;
		sum_ai = 0;
		val_first = val_last = val;
		best_len_prefix = best_len_suffix = best_len = 1;
	}
	static T_ ZERO() { return T_(); }

	inline bool is_zero() const { return left_i == 0 or right_i == 0; }
	inline bool is_single() const { return left_i == right_i; }
	inline int len() const { return right_i - left_i + 1; }

	void print() const {
		cerr 
			<< "| range: "
			<< setw(3) << left_i 
			<< setw(3) << right_i 
			<< "| sums: "
			<< setw(4) << sum_i
			<< setw(4) << sum_a
			<< setw(4) << sum_b
			<< setw(4) << sum_ai
			<< "| vals: "
			<< setw(4) << val_first
			<< setw(4) << val_last
			<< "| diffs: "
			<< setw(4) << diff_first
			<< setw(4) << diff_last
			<< "| best_lens: "
			<< setw(3) << best_len_prefix
			<< setw(3) << best_len_suffix
			<< setw(3) << best_len
			<< endl;
	}

	T_ operator + (const T_& right) {
		T_ res;
		T_& left = *this;

		if (left.is_zero())
			return right;

		if (right.is_zero())
			return left;

		res.sum_i  = left.sum_i  + right.sum_i;
		res.sum_a  = left.sum_a  + right.sum_a;
		res.sum_b  = left.sum_b  + right.sum_b;
		res.sum_ai = left.sum_ai + right.sum_ai;

		res.left_i  =  left.left_i;
		res.right_i = right.right_i;
		res.val_first =  left.val_first;
		res.val_last  = right.val_last;

		int64_t mid_diff = right.val_first - left.val_last;

		res.diff_first = ( left.is_single()) ? mid_diff : left.diff_first;
		res.diff_last  = (right.is_single()) ? mid_diff : right.diff_last;

		auto merge_parts = [&](int p1, int p2, bool cond_p1, bool cond_mid, bool cond_p2) {
			int res = p1;
			if (not cond_p1 or not cond_mid)
				return res;
			
			res += 1;
			if (not cond_p2)
				return res;

			res += p2 - 1;
			return res;
		};

		res.best_len_prefix = merge_parts(
			left.best_len_prefix,
			right.best_len_prefix,
			left.best_len_prefix == left.len(),
			mid_diff ==  left.diff_first or  left.is_single(),
			mid_diff == right.diff_first or right.is_single()
		);

		res.best_len_suffix = merge_parts(
			right.best_len_suffix,
			left.best_len_suffix,
			right.best_len_suffix == right.len(),
			mid_diff == right.diff_last  or right.is_single(),
			mid_diff ==  left.diff_last  or  left.is_single()
		);

		res.best_len = max(
			max(left.best_len, right.best_len),
			max(res.best_len_prefix, res.best_len_suffix)
		);

		if (left.diff_last == mid_diff)
			res.best_len = max(res.best_len, left.best_len_suffix + 1);

		if (mid_diff == right.diff_first)
			res.best_len = max(res.best_len, right.best_len_prefix + 1);

		if (left.diff_last == mid_diff and mid_diff == right.diff_first)
			res.best_len = max(
				res.best_len,
				left.best_len_suffix + right.best_len_prefix
			);

		/*
		cerr << "==================================" << endl;
		cerr << "left:  ";  left.print();
		cerr << "right: "; right.print();
		cerr << "-------mid_diff = " << mid_diff << "-----------------" << endl;
		cerr << "add:   ";   res.print();
		cerr << "==================================" << endl;
		*/

		return res;
	}

	T_ operator + (const F_& f) const {
		T_ res = *this;
		if (f._is_set) {
			res.sum_a   = f.da;
			res.sum_b   = f.db;
			res.sum_ai  = f.da * res.sum_i;

			res.val_first   = f.da * res.left_i  + f.db;
			res.val_last    = f.da * res.right_i + f.db;
			
			res.diff_first  = f.da;
			res.diff_last   = f.da;

			// Special case due to overwriting!
			res.best_len_prefix = res.best_len_suffix = res.best_len = res.len();
		}
		else {
			res.sum_a  += f.da;
			res.sum_b  += f.db;
			res.sum_ai += f.da * res.sum_i;
			
			res.val_first  += f.da * res.left_i  + f.db;
			res.val_last   += f.da * res.right_i + f.db;
			
			res.diff_first += f.da;
			res.diff_last  += f.da;
		}
		return res;
	}
	void operator += (const F_& oth) { (*this) = (*this) + oth; }
};

template <int N>
using SegmentTree = SegmentTree_<T_, F_, N>;

const int MAX = 3e5 + 7;
int N, Q;
int64_t arr[MAX];
SegmentTree<MAX> st;

void update_1(int l, int r, int64_t s, int64_t c) {
	st.update(l, r, F_::ADD(c, s - l * c));
}

void update_2(int l, int r, int64_t s, int64_t c) {
	st.update(l, r, F_::UPDATE(c, s - l * c));
}
	
int64_t evaluate(int l, int r) {
	return st.get(l, r).best_len;
}

void print(int l, int r) {
	for (int i = 1; i <= N; i++) {
		T_ node = st.get(i, i);
		int64_t x = node.sum_ai + node.sum_b;
		cerr << setw(5) << x;
	}
	cerr << endl;
}
	
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N >> Q;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	st.init(N, arr);

	while (Q--) {
		int t; cin >> t;
		if (t == 1) {
			int l, r; int64_t s, c;
			cin >> l >> r >> s >> c;
			update_1(l, r, s, c);
		}
		if (t == 2) {
			int l, r; int64_t s, c;
			cin >> l >> r >> s >> c;
			update_2(l, r, s, c);
		}
		if (t == 3) {
			int l, r;
			cin >> l >> r;
			cout << evaluate(l, r) << '\n';
			// print(l, r);
		}
	}

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17