結果

問題 No.674 n連勤
ユーザー nok0nok0
提出日時 2021-02-14 01:57:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 3,563 bytes
コンパイル時間 770 ms
コンパイル使用メモリ 84,720 KB
実行使用メモリ 4,548 KB
最終ジャッジ日時 2023-09-28 11:31:45
合計ジャッジ時間 2,175 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 13 ms
4,380 KB
testcase_14 AC 16 ms
4,384 KB
testcase_15 AC 13 ms
4,376 KB
testcase_16 AC 25 ms
4,548 KB
testcase_17 AC 25 ms
4,416 KB
testcase_18 AC 20 ms
4,376 KB
testcase_19 AC 14 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <iostream>
#include <limits>
#include <set>
#include <vector>

template <class T>
struct RangeSet {
private:
	const T TINF = std::numeric_limits<T>::max() / 2;
	std::set<std::pair<T, T>> st;

public:
	RangeSet() {
		st.emplace(-TINF, -TINF + 1);
		st.emplace(TINF, TINF + 1);
	}

	//[l, r) is covered?
	bool covered(const T l, const T r) {
		assert(l < r);
		auto itr = prev(st.lower_bound({l + 1, -TINF}));
		return itr->first <= l and r <= itr->second;
	}

	//[x, x + 1) is covered?
	bool covered(const T x) { return covered(x, x + 1); }

	//return section which covers[l, r)
	//if not exists, return[-TINF, -TINF)
	std::pair<T, T> covered_by(const T l, const T r) {
		assert(l < r);
		auto itr = prev(st.lower_bound({l + 1, -TINF}));
		if(itr->first <= l and r <= itr->second) return *itr;
		return {-TINF, -TINF};
	}

	//return section which covers[x, x + 1)
	//if not exists, return[-TINF, -TINF)
	std::pair<T, T> covered_by(const T x) { return covered_by(x, x + 1); }

	//insert[l, r), and return increment
	T insert(T l, T r) {
		if(l >= r) return 0;
		auto itr = prev(st.lower_bound({l + 1, -TINF}));
		if(itr->first <= l and r <= itr->second) return T(0);
		T sum_erased = T(0);
		if(itr->first <= l and l <= itr->second) {
			l = itr->first;
			sum_erased += itr->second - itr->first;
			itr = st.erase(itr);
		} else
			itr = next(itr);
		while(r > itr->second) {
			sum_erased += itr->second - itr->first;
			itr = st.erase(itr);
		}
		if(itr->first <= r) {
			sum_erased += itr->second - itr->first;
			r = itr->second;
			st.erase(itr);
		}
		st.emplace(l, r);
		return r - l - sum_erased;
	}

	//insert[x, x + 1), and return increment
	T insert(const T x) { return insert(x, x + 1); }

	// erase [l, r), and return decrement
	T erase(const T l, const T r) {
		assert(l < r);
		auto itr = prev(st.lower_bound({l + 1, -TINF}));
		if(itr->first <= l and r <= itr->second) {
			if(itr->first < l) st.emplace(itr->first, l);
			if(r < itr->second) st.emplace(r, itr->second);
			st.erase(itr);
			return r - l;
		}

		T ret = T(0);
		if(itr->first <= l and l < itr->second) {
			ret += itr->second - l;
			if(itr->first < l) st.emplace(itr->first, l);
			itr = st.erase(itr);
		} else
			itr = next(itr);
		while(itr->second <= r) {
			ret += itr->second - itr->first;
			itr = st.erase(itr);
		}
		if(itr->first < r) {
			ret += r - itr->first;
			st.emplace(r, itr->second);
			st.erase(itr);
		}
		return ret;
	}

	// erase [x, x + 1), and return decrement
	T erase(const T x) { return erase(x, x + 1); }

	int size() { return (int)st.size() - 2; }

	int mex(const T x = 0) {
		auto itr = prev(st.lower_bound({x + 1, -TINF}));
		if(itr->first <= x and x < itr->second)
			return itr->second;
		else
			return x;
	}

	T sum_all() const {
		T res = 0;
		for(auto &p : st) {
			if(std::abs(p.first) == TINF) continue;
			res += p.second - p.first;
		}
		return res;
	}

	std::set<std::pair<T, T>> get() const {
		std::set<std::pair<T, T>> res;
		for(auto &p : st) {
			if(std::abs(p.first) == TINF) continue;
			res.emplace(p.first, p.second);
		}
		return res;
	}

	void dump() const {
		std::cout << "Rangeset:";
		for(auto &p : st) {
			if(std::abs(p.first) == TINF) continue;
			std::cout << "[" << p.first << "," << p.second << "),";
		}
		std::cout << '\n';
	}
};

long long a, b, d, res;
int q;
int main() {
	scanf("%lld%d", &d, &q);
	RangeSet<long long> st;
	while(q--) {
		scanf("%lld%lld", &a, &b);
		st.insert(a, b + 1);
		auto [l, r] = st.covered_by(a);
		res = std::max(res, r - l);
		printf("%lld\n", res);
	}
}
0