#743153 (C++17) No.1860 Magnets

提出ソース

結果

問題	No.1860 Magnets
ユーザー	Ebishu
提出日時	2022-03-04 21:26:28
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	17,925 bytes
コンパイル時間	3,480 ms
コンパイル使用メモリ	212,696 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-18 19:15:03
合計ジャッジ時間	4,319 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	1 ms 5,376 KB
testcase_14	AC	1 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	1 ms 5,376 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	1 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB

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

コンパイルメッセージ

main.cpp: In member function 'int BitVector::select(int) const':
main.cpp:769:9: warning: no return statement in function returning non-void [-Wreturn-type]
  769 |         }
      |         ^

ソースコード

raw source code

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using lint = long long;
using P = pair<lint, lint>;
using Pii = pair<int, int>;

#define rep(i, n) for (lint i = 0; i < (lint)(n); ++i)
#define repe(i, n) for(lint i = 0; i <= (lint)(n); ++i)
#define rep1(i, n) for (lint i = 1; i < (lint)(n); ++i)
#define rep1e(i, n) for (lint i = 1; i <= (lint)(n); ++i)
#define repn(i, a, b) for (lint i = (a); i < (lint)(b); ++i)
#define repne(i, a, b) for (lint i = (a); i <= (lint)(b); ++i)
#define rrep(i, n) for (lint i = (n); i >= 0; --i)
#define all(vec) begin(vec), end(vec)
#define rall(vec) rbegin(vec), rend(vec)

constexpr long long Mod = /** 1000'000'007LL /*/ 998244353LL /**/;
constexpr long long Inf = 1'000'000'000'000'000'010LL;
constexpr int IntInf = 1000'000'010;
constexpr double Pi = 3.141592653589793238;
constexpr double InvPi = 0.318309886183790671;

const int di[4] = { 0,1,0,-1 }, dj[4] = { 1,0,-1,0 };

#if __has_include(<atcoder/all>)
#include <atcoder/all>

using namespace atcoder;
using mint = static_modint<Mod>;

inline istream& operator>>(istream& is, mint& rhs) {
	long long tmp;
	is >> tmp;
	rhs = tmp;
	return is;
}
inline ostream& operator<<(ostream& os, const mint& rhs) { return os << rhs.val(); }

mint lagrange_interpolation(const vector<mint>& y, mint t) {
	const int n = (int)y.size();

	mint res = 0;

	vector<mint> inv(n), fact_inv(n);

	inv[1] = 1;
	fact_inv[0] = 1;
	fact_inv[1] = 1;
	for (int i = 2; i < n; ++i) {
		inv[i] = -Mod / i * inv[Mod % i];
		fact_inv[i] = fact_inv[i - 1] * inv[i];
	}

	vector<mint> prod2(n);
	prod2.back() = 1;
	for (int i = n - 1; i > 0; --i) {
		prod2[i - 1] = (t - i) * prod2[i];
	}

	mint prod1 = 1;
	for (int i = 0; i < n; ++i) {
		mint a = y[i];
		a *= fact_inv[i] * fact_inv[n - 1 - i];
		if ((n - 1 - i) & 1) a = -a;

		res += a * prod1 * prod2[i];

		prod1 *= (t - i);
	}

	return res;
}

template<typename T>
lint inversion_number(const vector<T> vec) {
	vector<T> v = vec;
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	const int n = vec.size();

	lint res = 0;

	fenwick_tree<int> b(n);
	for (int i = 0; i < n; ++i) {
		const int j = lower_bound(v.begin(), v.end(), vec[i]) - v.begin();
		res += i - b.sum(0, j);
		b.add(j, 1);
	}

	return res;
}

// Π(a_i x + b_i)
vector<mint> prod(const vector<mint>& a, const vector<mint>& b) {
	const size_t n = a.size();
	size_t n1 = 1;
	while (n1 < n) n1 <<= 1;

	vector<vector<mint>> fs(2 * n1, { 1 });
	for (size_t i = n1; i < n + n1; ++i) {
		fs[i].resize(2);
		fs[i][0] = b[i - n1];
		fs[i][1] = a[i - n1];
	}
	for (size_t i = n1 - 1; i >= 1; --i) {
		fs[i] = convolution(fs[i << 1], fs[i << 1 | 1]);
	}

	return fs[1];
}
#endif

template<typename T> using prique = priority_queue<T>;
template<typename T> using prique_inv = priority_queue<T, vector<T>, greater<T>>;
template<typename T> inline istream& operator>>(istream& is, vector<T>& v) { for (auto&& e : v) is >> e; return is; }
template<typename T> inline istream& operator>>(istream& is, complex<T>& c) {
	double real, imag;
	is >> real >> imag;
	c.real(real);
	c.imag(imag);
	return is;
}
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) {
	for (auto itr = v.begin(), end_itr = v.end(); itr != end_itr;) {
		os << *itr;
		if (++itr != end_itr) os << " ";
	}
	return os;
}
template<typename T, typename U> inline bool chmin(T& a, const U b) { return a > b ? a = b, true : false; }
template<typename T, typename U> inline bool chmax(T& a, const U b) { return a < b ? a = b, true : false; }
template<typename T, typename U> inline istream& operator>>(istream& is, pair<T, U>& rhs) { return is >> rhs.first >> rhs.second; }
template<typename T, typename U> inline ostream& operator<<(ostream& os, const pair<T, U>& rhs) { return os << "{" << rhs.first << ", " << rhs.second << "}"; }
template<typename T, typename U, class Pr> inline int getid(const vector<T>& v, const U& value, Pr pred) { return lower_bound(v.begin(), v.end(), value, pred) - v.begin(); }
template<typename T, typename U> inline int getid(const vector<T>& v, const U& value) { return getid(v, value, less<>{}); }

template<typename T> T gcd(const vector<T>& vec) {
	T res = vec.front();
	for (T e : vec) {
		res = gcd(res, e);
		if (res == 1) return 1;
	}
	return res;
}
template<typename T> T gcd(initializer_list<T> init) {
	auto first = init.begin(), last = init.end();
	T res = *(first++);
	for (auto itr = first; itr != last; ++itr) {
		res = gcd(res, *itr);
		if (res == 1) return 1;
	}
	return res;
}
template<typename T> T lcm(const vector<T>& vec) {
	T res = vec.front();
	for (T e : vec) res = lcm(res, e);
	return res;
}
template<typename T> T lcm(initializer_list<T> init) {
	auto first = init.begin(), last = init.end();
	T res = *(first++);
	for (auto itr = first; itr != last; ++itr) {
		res = lcm(res, *itr);
	}
	return res;
}
template<typename T> T pow(T x, lint n) {
	T res = 1;
	while (n > 0) {
		if (n & 1) res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}

inline void YESNO(bool b) { cout << (b ? "YES" : "NO") << "\n"; }
inline void YesNo(bool b) { cout << (b ? "Yes" : "No") << "\n"; }
inline void yesno(bool b) { cout << (b ? "yes" : "no") << "\n"; }

constexpr int bitpopcount(lint x) {
	x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);
	x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
	x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f0f0f0f0f);
	x = (x & 0x00ff00ff00ff00ff) + ((x >> 8) & 0x00ff00ff00ff00ff);
	x = (x & 0x0000ffff0000ffff) + ((x >> 16) & 0x0000ffff0000ffff);
	x = (x & 0x00000000ffffffff) + ((x >> 32) & 0x00000000ffffffff);
	return x;
}

template<typename T>
T rand(T l, T r) {
	static mt19937 mt(random_device{}());
	if constexpr (is_integral_v<T>) {
		static uniform_int_distribution<T> dist(l, r);
		return dist(mt);
	}
	else if constexpr (is_floating_point_v<T>) {
		static uniform_real_distribution<T> dist(l, r);
		return dist(mt);
	}
}

bool is_prime(lint x) {
	for (lint i = 2; i * i <= x; ++i) {
		if (x % i == 0) return false;
	}
	return 1 < x;
}

vector<lint> divisors(lint n) {
	vector<lint> res;
	for (lint x = 1; x * x <= n; ++x) {
		if (n % x == 0) {
			res.push_back(x);
			if (x * x != n) res.push_back(n / x);
		}
	}
	return res;
}

lint phi(lint n) {
	lint r = n;
	for (lint i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			r -= r / i;
			while (n % i == 0) n /= i;
		}
	}
	if (n > 1) r -= r / n;
	return r;
}

lint floor_sqrt(lint n) {
	lint l = 0, r = 3000'000'000LL;
	while (r - l > 1) {
		lint mid = (l + r) / 2;
		(mid * mid <= n ? l : r) = mid;
	}
	return l;
}

lint ceil_sqrt(lint n) {
	lint l = 0, r = 3000'000'000LL;
	while (r - l > 1) {
		lint mid = (l + r) / 2;
		(mid * mid < n ? l : r) = mid;
	}
	return r;
}

template<typename T>
constexpr bool is_intersect(T l1, T r1, T l2, T r2) {
	return l1 <= r2 && l2 <= r1;
}

lint fact[15'000'020], fact_inv[15'000'020], inv[15'000'020];
void fact_init(lint n) {
	fact[0] = fact[1] = 1;
	fact_inv[0] = fact_inv[1] = 1;
	inv[1] = 1;

	for (lint i = 2; i <= n; ++i) {
		fact[i] = i * fact[i - 1] % Mod;
		inv[i] = Mod - Mod / i * inv[Mod % i] % Mod;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % Mod;
	}
}

lint modinv(lint a, lint m = Mod) {
	lint b = m, u = 1, v = 0;
	while (b != 0) {
		lint t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

lint modpow(lint x, lint n, lint m = Mod) {
	if (m == 1) return 0;
	lint res = 1;
	x %= m;
	while (n > 0) {
		if (n & 1) res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

lint intpow(lint x, lint n) {
	lint res = 1;
	while (n > 0) {
		if (n & 1) res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}

inline lint comb(lint n, lint r) {
	if (n < 0 || r < 0 || n < r) return 0;
	if (r == 0 || r == n) return 1;
	return fact[n] * fact_inv[n - r] % Mod * fact_inv[r] % Mod;
}

inline lint perm(lint n, lint r) {
	if (n < 0 || r < 0 || n < r) return 0;
	return fact[n] * fact_inv[n - r] % Mod;
}

template<typename T = int>
vector<T> as_vector(const string& str) {
	vector<T> res(str.size());

	auto p_res = res.begin();
	auto p_str = str.begin();
	auto end_str = str.end();

	while(p_str != end_str) {
		*p_res++ = *p_str++ - '0';
	}

	return res;
}

template<typename T>
vector<T> compressed(vector<T> v) {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	return v;
}

template<typename T>
vector<int> compressed_index(vector<T> v) {
	const int n = v.size();
	const auto c = compressed(v);
	vector<int> res(n);
	for (int i = 0; i < n; ++i) {
		res[i] = lower_bound(all(c), v[i]) - c.begin();
	}
	return res;
}

// { 値, 個数 }
template<typename T>
pair<vector<T>, vector<int>> compressed_pair(vector<T> v) {
	size_t n = v.size();
	sort(all(v));
	vector<T> cnt, val;
	cnt.reserve(n); val.reserve(n);
	int now_cnt = 1;
	for (size_t i = 1; i < n; ++i) {
		if (v[i - 1] != v[i]) {
			cnt.push_back(now_cnt);
			val.push_back(v[i - 1]);
			now_cnt = 1;
		}
		else ++now_cnt;
	}
	cnt.push_back(now_cnt);
	val.push_back(v.back());

	return { val, cnt };
}

class Factring {
private:

	const lint max_n;
	vector<lint> sieve;

public:

	explicit Factring(lint max_n)
		: max_n(max_n)
		, sieve(max_n + 1)
	{
		iota(sieve.begin(), sieve.end(), 0);

		for (lint i = 2; i * i <= max_n; ++i) {
			if (sieve[i] < i) continue;

			for (lint j = i * i; j <= max_n; j += i) {
				if (sieve[j] == j) sieve[j] = i;
			}
		}
	}

	unordered_map<lint, lint> calc(lint x) const {
		unordered_map<lint, lint> res;
		while (x > 1) {
			++res[sieve[x]];
			x /= sieve[x];
		}
		return res;
	}
};

struct UnionFind {
	int n;
	vector<int> par, rank, siz, es;
	int c;

	UnionFind() = default;

	explicit UnionFind(int _n)
		: n(_n)
		, par(_n)
		, rank(_n)
		, siz(_n, 1)
		, es(_n)
		, c(_n)
	{
		iota(par.begin(), par.end(), 0);
	}

	int root(int x) {
		while (par[x] != x) {
			x = par[x] = par[par[x]];
		}

		return x;
	}

	bool same(int x, int y) { return root(x) == root(y); }

	void unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) ++es[x];
		else {
			c--;
			if (rank[x] < rank[y]) {
				par[x] = y;
				siz[y] += siz[x];
				es[y] += es[x] + 1;
			}
			else {
				par[y] = x;
				if (rank[x] == rank[y]) ++rank[x];
				siz[x] += siz[y];
				es[x] += es[y] + 1;
			}
		}
	}

	int count(int x) { return siz[root(x)]; }

	vector<vector<int>> groups() {
		vector<int> roots(n), group_size(n);

		for (int i = 0; i < n; ++i) {
			roots[i] = root(i);
			++group_size[roots[i]];
		}

		vector<vector<int>> res(n);

		for (int i = 0; i < n; ++i) {
			res.reserve(group_size[i]);
		}

		for (int i = 0; i < n; ++i) {
			res[roots[i]].push_back(i);
		}

		res.erase(
			remove_if(res.begin(), res.end(),
				[](const vector<int>& v) { return v.empty(); }),
			res.end()
		);

		return res;
	}
};

template<typename T>
class CumulativeSum {
private:

	const int n;
	vector<T> dat;

public:

	CumulativeSum() = default;
	explicit CumulativeSum(const int n) : n(n), dat(n + 1) {}
	CumulativeSum(const vector<T>& vec)
		: n(vec.size())
		, dat(n + 1)
	{
		for (int i = 0; i < n; ++i) dat[i + 1] = vec[i];
	}

	void add(const int i, const T& x) { dat[i + 1] += x; }

	void build() {
		for (int i = 0; i < n; ++i) {
			dat[i + 1] += dat[i];
		}
	}

	// [l, r)
	T sum(const int l, const int r) const { return dat[r] - dat[l]; }

	// [0, a)
	T sum(const int a) const { return dat[a]; }
};

template<typename T>
class CumulativeSum2D {
private:

	vector<vector<T>> dat;

public:

	CumulativeSum2D() = default;

	explicit CumulativeSum2D(size_t n) : dat(n + 1, vector<T>(n + 1)) {}

	CumulativeSum2D(size_t h, size_t w) : dat(h + 1, vector<T>(w + 1)) {}

	CumulativeSum2D(const vector<vector<T>>& vec) {
		const size_t h = vec.size(), w = vec.front().size();

		dat.resize(h + 1, vector<T>(w + 1));

		for (size_t i = 0; i < h; ++i) {
			for (size_t j = 0; j < w; ++j) {
				dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j] + vec[i][j];
			}
		}
	}

	void add(int h, int w, int v) {
		dat[h + 1][w + 1] += v;
	}

	void build() {
		const size_t h = dat.size() - 1, w = dat.front().size() - 1;
		for (size_t i = 0; i < h; ++i) {
			for (size_t j = 0; j < w; ++j) {
				dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j];
			}
		}
	}

	// [0, h) × [0, w)
	T sum(int h, int w) const {
		return sum(0, 0, h, w);
	}

	// [h1, h2) × [w1, w2)
	T sum(int h1, int w1, int h2, int w2) const {
		return dat[h2][w2] - dat[h1][w2] - dat[h2][w1] + dat[h1][w1];
	}
};

template<typename T>
class BinaryIndexedTree {
private:

	const int size;
	vector<T> dat;

public:

	explicit BinaryIndexedTree(const int size)
		: size(size)
		, dat(size + 1) {}

	explicit BinaryIndexedTree(const vector<T>& vec)
		: size(vec.size())
		, dat(size + 1)
	{
		for (int i = 0; i < size; ++i) dat[i + 1] = vec[i];
		for (int i = 0; i <= size; ++i) {
			const int j = i + (i & -i);
			if (j <= size) dat[j] += dat[i];
		}
	}

	// 0-indexed
	void add(const int a, const T v) {
		for (int x = a + 1; x <= size; x += (x & -x)) dat[x] += v;
	}

	// 0-indexed
	void set(const int a, const T v) {
		add(a, v - dat[a]);
	}

	// [0, a)
	T sum(const int a) const {
		T res = 0;
		for (int x = a; x > 0; x -= x & -x) res += dat[x];
		return res;
	}

	// [a, b)
	T sum(const int a, const int b) const { return sum(b) - sum(a); }

	const T& operator[](const size_t x) const  { return dat[x + 1]; }
};

struct Point {
	lint x, y;

	Point() = default;
	constexpr Point(lint x_, lint y_) : x(x_), y(y_) {}
	
	constexpr bool operator<(const Point& p) const {
		if (x != p.x) return x < p.x;
		return y < p.y;
	}

	constexpr Point operator+() const { return *this; }
	constexpr Point operator-() const { return { -x, -y }; }
	constexpr Point operator+(const Point& p) const { return { x + p.x, y + p.y }; }
	constexpr Point operator-(const Point& p) const { return { x - p.x, y - p.y }; }
	constexpr Point operator*(lint s) const { return { x * s, y * s }; }
	constexpr Point& operator+=(const Point& p) {
		x += p.x; y += p.y;
		return *this;
	}
	constexpr Point& operator-=(const Point& p) {
		x -= p.x; y -= p.y;
		return *this;
	}

	constexpr lint dot(const Point& p) const { return x * p.x + y * p.y; }
	constexpr lint cross(const Point& p) const { return x * p.y - y * p.x; }

	constexpr lint lengthSq() const { return x * x + y * y; }
	double length() const { return hypot(x, y); }
	constexpr lint distanceSq(const Point& p) const { return (*this - p).lengthSq(); }
	double distance(const Point& p) const { return (*this - p).length(); }

	friend constexpr Point operator*(lint s, const Point& p) { return p * s; }
	friend istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; }
};

template<typename T, typename U>
T nearest_value(const vector<T>& v, const U& value) {
	auto itr = lower_bound(v.begin(), v.end(), value);
	if (itr == v.begin()) return *itr;
	if (itr == v.end()) return *prev(itr);
	return min(*itr - value, value - *prev(itr)) + value;
}

class BitVector {
public:
	using u8 = uint8_t;
	using u16 = uint16_t;

	int n, l;
	static constexpr int small_per_large = 32;
	static constexpr int large_size = 256, small_size = 8;

	vector<u8> bit;
	vector<u16> large;
	vector<vector<u8>> small;

	static inline const vector<u8> table = {
		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
	};

	explicit BitVector(int _n)
		: n(_n)
		, l((_n + large_size - 1) / large_size)
	{
		bit.assign(l * small_per_large, 0);
		large.assign(l + 1, 0);
		small.assign(l, vector<u8>(small_per_large, 0));
	}
	
	explicit BitVector(vector<bool> vec)
		: n(vec.size())
		, l((n + large_size - 1) / large_size)
	{
		bit.resize(l * small_per_large);
		large.assign(l + 1, 0);
		small.assign(l, vector<u8>(small_per_large, 0));

		for (int i = 0; i < n; ++i) set(i, vec[i]);
	}

	void set(int p, bool b) {
		const int bp = p >> 8;
		const int a = p & 7;
		if (b) bit[bp] |= 1 << a;
		else bit[bp] &= ~(1 << a);
	}

	bool get(int p) const {
		const int bp = p >> 8;
		const int a = p & 7;
		return bit[bp] >> a & 1;
	}

	void build() {
		large[0] = 0;
		for (int i = 0; i < l; ++i) {
			small[i][0] = 0;
			for (int j = 0; j < small_per_large - 1; ++j) {
				small[i][j + 1] = small[i][j] + table[bit[small_per_large * i + j]];
			}
			large[i + 1] = large[i] + small[i][small_per_large - 1] + table[bit[small_per_large * i + small_per_large - 1]];
		}
	}

	// [0, p)
	int rank(int p) const {
		const int lp = p >> 8;
		const int sp = (p & 255) >> 3;
		const int a = p & 7;

		const int rem = bit[p >> 3] & ((1 << a) - 1);

		return large[lp] + small[lp][sp] + table[rem];
	}


	int select(int n) const {
		// todo
	}
};

int main() {
	lint a, b;
	cin >> a >> b;

	if (a > b) swap(a, b);

	int d = b - a, ans = 2 * a;
	if (d <= 1) ans += d;
	else {
		ans += 1;
		d -= 1;
		ans += 2 * d;
	}

	cout << ans << endl;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード