結果

問題 No.674 n連勤
ユーザー nok0
提出日時 2021-02-14 01:57:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 3,563 bytes
コンパイル時間 1,591 ms
コンパイル使用メモリ 82,600 KB
最終ジャッジ日時 2025-01-18 20:16:10
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:144:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  144 |         scanf("%lld%d", &d, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:147:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  147 |                 scanf("%lld%lld", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

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