尺取り法 (daylight/double_pointer.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/double_pointer.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)

Verified with

• test/aoj/dsl/3_C.test.cpp

Code

#include "daylight/base.hpp"

/// @brief 尺取り法

/// @brief 各lについてcheck(l,r)==trueになる最小のrを求める。
/// @param left 探索範囲の左端(inclusive)
/// @param right 探索範囲の右端(exclusive)
/// @param check ()->現在の範囲が条件を満たすか
/// @param add (インデックス,左からの操作か)
/// @param del (インデックス,左からの操作か)
/// @param update 各lについてcheck(l,r)==trueになる最大のrとともに1度のみ呼ばれる
void doublePointerMinRight(
	int left, int right, function<bool()> check,
	function<void(int, bool)> add,
	function<void(int, bool)> del,
	function<void(int, int)> update) {
	int r = left;
	for(int l = left; l < right; l++) {
		while(r < right && !check()) {
			add(r++, false);
		}
		if(!check()) break;
		update(l, r);
		del(l, true);
	}
}

/// @brief 各lについてcheck(l,r)==trueになる最大のrを求める。
/// @param left 探索範囲の左端(inclusive)
/// @param right 探索範囲の右端(exclusive)
/// @param check ()->現在の範囲が条件を満たすか
/// @param add (インデックス,左からの操作か)
/// @param del (インデックス,左からの操作か)
/// @param update 各lについてcheck(l,r)==trueになる最大のrとともに1度のみ呼ばれる
void doublePointerMaxRight(
	int left, int right, function<bool()> check,
	function<void(int, bool)> add,
	function<void(int, bool)> del,
	function<void(int, int)> update) {
	int r = left;
	for(int l = left; l < right; l++) {
		while(r < right) {
			add(r++, false);
			if(!check()) {
				r--;
				del(r, false);
				break;
			}
		}
		update(l, r);
		if(l == r) {
			r++;
		} else {
			del(l, true);
		}
	}
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page