結果
| 問題 | No.1860 Magnets |
| ユーザー |
 Ebishu
|
| 提出日時 | 2022-03-04 21:26:28 |
| 言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 17,925 bytes |
| コンパイル時間 | 4,654 ms |
| コンパイル使用メモリ | 210,056 KB |
| 実行使用メモリ | 4,388 KB |
| 最終ジャッジ日時 | 2023-09-25 23:45:18 |
| 合計ジャッジ時間 | 5,345 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,380 KB |
| testcase_03 | AC | 2 ms
4,380 KB |
| testcase_04 | AC | 2 ms
4,380 KB |
| testcase_05 | AC | 2 ms
4,380 KB |
| testcase_06 | AC | 2 ms
4,380 KB |
| testcase_07 | AC | 2 ms
4,380 KB |
| testcase_08 | AC | 2 ms
4,380 KB |
| testcase_09 | AC | 2 ms
4,380 KB |
| testcase_10 | AC | 1 ms
4,380 KB |
| testcase_11 | AC | 2 ms
4,376 KB |
| testcase_12 | AC | 1 ms
4,376 KB |
| testcase_13 | AC | 1 ms
4,376 KB |
| testcase_14 | AC | 1 ms
4,388 KB |
| testcase_15 | AC | 2 ms
4,376 KB |
| testcase_16 | AC | 2 ms
4,380 KB |
| testcase_17 | AC | 1 ms
4,380 KB |
| testcase_18 | AC | 2 ms
4,376 KB |
| testcase_19 | AC | 2 ms
4,376 KB |
| testcase_20 | AC | 1 ms
4,380 KB |
| testcase_21 | AC | 1 ms
4,380 KB |
| testcase_22 | AC | 1 ms
4,380 KB |
| testcase_23 | AC | 1 ms
4,376 KB |
| testcase_24 | AC | 1 ms
4,376 KB |
| testcase_25 | AC | 1 ms
4,384 KB |
| testcase_26 | AC | 1 ms
4,380 KB |
| testcase_27 | AC | 2 ms
4,380 KB |
| testcase_28 | AC | 1 ms
4,380 KB |
| testcase_29 | AC | 2 ms
4,380 KB |
コンパイルメッセージ
main.cpp: メンバ関数 ‘int BitVector::select(int) const’ 内:
main.cpp:769:9: 警告: 非 void を戻す関数内に return 文がありません [-Wreturn-type]
769 | }
| ^
ソースコード
#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;
}