#465776 (C++14) No.1028 闇討ち

提出ソース
結果

問題	No.1028 闇討ち
ユーザー	kaage
提出日時	2020-04-17 21:57:47
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	868 ms / 2,000 ms
コード長	20,725 bytes
コンパイル時間	3,380 ms
コンパイル使用メモリ	165,160 KB
実行使用メモリ	25,136 KB
最終ジャッジ日時	2024-11-14 22:20:07
合計ジャッジ時間	12,140 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	3 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	3 ms 6,816 KB
testcase_09	AC	30 ms 6,816 KB
testcase_10	AC	44 ms 6,820 KB
testcase_11	AC	182 ms 9,728 KB
testcase_12	AC	813 ms 24,304 KB
testcase_13	AC	804 ms 24,160 KB
testcase_14	AC	444 ms 18,620 KB
testcase_15	AC	136 ms 8,832 KB
testcase_16	AC	868 ms 24,920 KB
testcase_17	AC	864 ms 24,788 KB
testcase_18	AC	865 ms 24,988 KB
testcase_19	AC	864 ms 24,960 KB
testcase_20	AC	866 ms 24,716 KB
testcase_21	AC	865 ms 25,136 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i, n) for(int i=0;i<(n);i++)
#define REP(i, n) for(int i=1;i<=(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef std::pair<lint, lint> P;
constexpr int INF = INT_MAX;
constexpr lint LINF = LLONG_MAX;
constexpr double eps = 1e-9;
template<class T>
class prique :std::priority_queue<T, std::vector<T>, std::greater<T>> {};
using namespace std;
template<class T, class Alloc = std::allocator<T>>
class Vector {

	using traits = std::allocator_traits<Alloc>;

	using size_type = unsigned int;

	class iterator {

	public:

		using difference_type = int;
		using value_type = T;
		using pointer = T*;
		using reference = T&;
		using iterator_category = std::random_access_iterator_tag;

	private:

		T* p;

	public:

		iterator()noexcept :p(nullptr) {}
		iterator(Vector* base, difference_type index) noexcept :p(base->e + index) {}
		iterator(const iterator& i) :p(i.p) {}

		iterator& operator=(const iterator& i) = default;

		iterator& operator++() {
			p++;
			return *this;
		}

		iterator operator++(int) {
			iterator res = *this;
			p++;
			return res;
		}

		iterator operator+(const difference_type& x)const {
			return iterator(*this) += x;
		}

		iterator& operator+=(const difference_type& x) {
			p += x;
			return *this;
		}

		iterator& operator--() {
			p--;
			return *this;
		}

		iterator operator--(int) {
			iterator res = *this;
			p--;
			return res;
		}

		iterator operator-(const difference_type& x)const {
			return iterator(*this) -= x;
		}

		difference_type operator-(const iterator& i)const {
			return p - i.p;
		}

		iterator& operator-=(const difference_type& x) {
			p -= x;
			return *this;
		}

		reference operator*()const {
			return *p;
		}

		reference operator[](const difference_type& x)const {
			return *(p + x);
		}

		bool operator<(const iterator& i)const {
			return p < i.p;
		}

		bool operator<=(const iterator& i)const {
			return p <= i.p;
		}

		bool operator==(const iterator& i)const {
			return p == i.p;
		}

		bool operator>(const iterator& i)const {
			return p > i.p;
		}

		bool operator>=(const iterator& i)const {
			return p >= i.p;
		}

		bool operator!=(const iterator& i)const {
			return p != i.p;
		}

	};

	class const_iterator {

	public:

		using difference_type = int;
		using value_type = T;
		using pointer = const T*;
		using reference = const T&;
		using iterator_category = std::random_access_iterator_tag;

	private:

		const T* p;

	public:

		const_iterator()noexcept :p(nullptr) {}
		const_iterator(Vector* base, difference_type index) noexcept :p(base->e + index) {}
		const_iterator(const iterator& i) :p(i.p) {}
		const_iterator(const const_iterator& i) :p(i.p) {}

		const_iterator& operator=(const const_iterator& i) = default;

		const_iterator& operator++() {
			p++;
			return *this;
		}

		const_iterator operator++(int) {
			const_iterator res = *this;
			p++;
			return res;
		}

		const_iterator operator+(const difference_type& x)const {
			return const_iterator(*this) += x;
		}

		const_iterator& operator+=(const difference_type& x) {
			p += x;
			return *this;
		}

		const_iterator& operator--() {
			p--;
			return *this;
		}

		const_iterator operator--(int) {
			const_iterator res = *this;
			p--;
			return res;
		}

		const_iterator operator-(const difference_type& x)const {
			return const_iterator(*this) -= x;
		}

		difference_type operator-(const const_iterator& i)const {
			return p - i.p;
		}

		const_iterator& operator-=(const difference_type& x) {
			p -= x;
			return *this;
		}

		reference operator*()const {
			return *p;
		}

		reference operator[](const difference_type& x)const {
			return *(p + x);
		}

		bool operator<(const const_iterator& i)const {
			return p < i.p;
		}

		bool operator<=(const const_iterator& i)const {
			return p <= i.p;
		}

		bool operator==(const const_iterator& i)const {
			return p == i.p;
		}

		bool operator>(const const_iterator& i)const {
			return p > i.p;
		}

		bool operator>=(const const_iterator& i)const {
			return p >= i.p;
		}

		bool operator!=(const const_iterator& i)const {
			return p != i.p;
		}

	};

	using reverse_iterator = std::reverse_iterator<iterator>;
	using const_reverse_iterator = std::reverse_iterator<const_iterator>;

private:

	T* e;
	unsigned int length = 0, cap = 1;
	Alloc alloc;

	static_assert(std::is_same<T, typename Alloc::value_type>::value, "The allocator value type is not matched the vector value type.");
	static_assert(!std::is_const<T>::value, "This library forbids containers of const elements");

public:

	Vector() :Vector(Alloc()) {}

	explicit Vector(const Alloc& a) :alloc(a) {
		e = alloc.allocate(cap);
	}

	explicit Vector(size_type n, const Alloc& a = Alloc()) :alloc(a) {
		while (cap < n)cap *= 2;
		e = alloc.allocate(cap);
		rep(i, n)emplace_back();
	}

	explicit Vector(size_type n, const T& value, const Alloc& a = Alloc()) :alloc(a) {
		while (cap < n)cap *= 2;
		e = alloc.allocate(cap);
		rep(i, n)emplace_back(value);
	}

	template<class InputIter>
	Vector(InputIter first, InputIter last, const Alloc& a = Alloc()) :alloc(a) {
		e = alloc.allocate(cap);
		for (InputIter i = first; i != last; i++) {
			emplace_back(*i);
		}
	}

	Vector(const Vector& x, const Alloc& a = Alloc()) :alloc(a) {
		while (cap < x.length)cap *= 2;
		length = x.length;
		e = alloc.allocate(cap);
		rep(i, x.length)traits::construct(alloc, e + i, *(x.e + i));
	}

	Vector(Vector&& x, const Alloc& a = Alloc()) :alloc(a) {
		cap = x.cap;
		length = x.length;
		e = x.e;
		x.e = nullptr;
	}

	~Vector() {
		if (e != nullptr) {
			rep(i, length)traits::destroy(alloc, e + i);
			alloc.deallocate(e, cap);
		}
	}

	Vector& operator=(const Vector& x) {
		rep(i, length)traits::destroy(alloc, e + i);
		alloc.deallocate(e, cap);
		length = x.length;
		cap = 1;
		while (cap < length)cap *= 2;
		e = alloc.allocate(cap);
		rep(i, length)traits::construct(alloc, e + i, *(x.e + i));
		return *this;
	}

	Vector& operator=(Vector&& x) {
		rep(i, length)traits::destroy(alloc, e + i);
		alloc.deallocate(e, cap);
		cap = x.cap;
		length = x.length;
		e = x.e;
		x.e = nullptr;
		return *this;
	}

private:

	void extension() {
		T* e_ = alloc.allocate(cap * 2);
		rep(i, length)traits::construct(alloc, e_ + i, *(e + i));
		rep(i, length)traits::destroy(alloc, e + i);
		alloc.deallocate(e, cap);
		e = e_;
		cap *= 2;
	}

	void extension(size_type n) {
		unsigned int r = 1;
		while (cap * r < n)r *= 2;
		if (r == 1)return;
		T* e_ = alloc.allocate(cap * r);
		rep(i, length)traits::construct(alloc, e_ + i, *(e + i));
		rep(i, length)traits::destroy(alloc, e + i);
		alloc.deallocate(e, cap);
		e = e_;
		cap *= r;
	}

public:

	template<class InputIter>
	void assign(InputIter first, InputIter last) {
		unsigned int cnt = 0;
		for (InputIter i = first; i != last; i++) {
			if (cnt == cap) {
				length = std::max(length, cnt);
				extension();
			}
			traits::construct(alloc, e + cnt, *i);
			cnt++;
		}
	}

	void assign(size_type n, const T& value) {
		extension(n);
		std::fill(e, e + n, value);
	}

	template<class... Args>
	void emplace_back(Args&&... args) {
		if (length == cap)extension();
		traits::construct(alloc, e + length, std::forward<Args>(args)...);
		length++;
	}

	void push_back(const T& value) {
		emplace_back(value);
	}

	void push_back(T&& value) {
		emplace_back(std::move(value));
	}

	void pop_back() {
		traits::destroy(alloc, e + length);
		length--;
	}

	iterator erase(iterator pos) {
		const iterator res = pos;
		iterator t = pos; t++;
		for (iterator i = pos; t != end(); i++, t++) {
			*i = std::move(*t);
		}
		pop_back();
		return res;
	}

	iterator erase(iterator first, iterator last) {
		const iterator res = first;
		typename iterator::difference_type d = last - first;
		for (iterator i = first; i + d != end(); i++) {
			*i = std::move(*(i + d));
		}
		rep(i, d)pop_back();
		return res;
	}

	void swap(Vector& x) {
		std::swap(length, x.length);
		std::swap(cap, x.cap);
		std::swap(e, x.e);
	}

	void clear() {
		while (length)pop_back();
	}

	size_type size()const {
		return length;
	}

	void resize(size_type  n, const T& value = T()) {
		extension(n);
		while (n < length)pop_back();
		std::fill(e, e + n, value);
	}

	size_type capacity()const {
		return cap;
	}

	bool empty()const {
		return !length;
	}

	T& operator[](const unsigned int pos) {
		return e[pos];
	}

	T* data() {
		return e;
	}

	T& front() {
		return *e;
	}

	T& back() {
		return *(e + length - 1);
	}

	iterator begin() noexcept {
		return iterator(this, 0);
	}

	const_iterator begin()const noexcept {
		return const_iterator(this, 0);
	}

	const_iterator cbegin()const noexcept {
		return const_iterator(this, 0);
	}

	iterator rbegin()noexcept {
		return reverse_iterator(this, 0);
	}

	const_iterator rbegin()const noexcept {
		return const_reverse_iterator(this, 0);
	}

	const_iterator crbegin()const noexcept {
		return const_reverse_iterator(this, 0);
	}

	iterator end() noexcept {
		return iterator(this, length);
	}

	const_iterator end()const noexcept {
		return const_iterator(this, length);
	}

	const_iterator cend()const noexcept {
		return const_iterator(this, length);
	}

	iterator rend()noexcept {
		return reverse_iterator(this, length);
	}

	const_iterator rend()const noexcept {
		return const_reverse_iterator(this, length);
	}

	const_iterator crend()const noexcept {
		return const_reverse_iterator(this, length);
	}

};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
lint mypow(lint a, lint b) {
	if (!b)return 1;
	if (b & 1)return mypow(a, b - 1) * a;
	lint memo = mypow(a, b >> 1);
	return memo * memo;
}
lint modpow(lint a, lint b, lint m) {
	if (!b)return 1;
	if (b & 1)return modpow(a, b - 1, m) * a % m;
	lint memo = modpow(a, b >> 1, m);
	return memo * memo % m;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size() - 1)std::cout << vec[i] << " ";
	std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(Vector<T>& vec) {
	rep(i, vec.size() - 1)std::cout << vec[i] << " ";
	std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(T l, T r) {
	T rprev = r;
	rprev--;
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
std::string to_string(Vector<int>& vec) {
	std::string res = "[";
	rep(i, vec.size() - 1)res += std::to_string(vec[i]) + ", ";
	res += std::to_string(vec.back()) + "]";
	return res;
}
template<typename T, typename U>
class SegTree {
protected:
	int n = 1, rank = 0;
	vector<T> node;
	vector<U> lazy;
	vector<bool> lazyflag;
	vector<int> width;
	virtual void lazyf(U&, const U&) = 0;
	virtual void updf(T&, const U&, const unsigned int&) = 0;
	void eval(int k) {
		if (!k)return;
		for (int i = rank; i > 0; i--) {
			int nk = k >> i;
			if (lazyflag[nk]) {
				updf(node[2 * nk], lazy[nk], width[2 * nk]);
				updf(node[2 * nk + 1], lazy[nk], width[2 * nk + 1]);
				if (lazyflag[2 * nk])lazyf(lazy[2 * nk], lazy[nk]);
				else lazy[2 * nk] = lazy[nk];
				if (lazyflag[2 * nk + 1])lazyf(lazy[2 * nk + 1], lazy[nk]);
				else lazy[2 * nk + 1] = lazy[nk];
				lazyflag[2 * nk] = lazyflag[2 * nk + 1] = true;
				lazyflag[nk] = false;
			}
		}
	}
public:
	SegTree(unsigned int m, T init) {
		while (n < m) {
			n *= 2;
			rank++;
		}
		node.resize(2 * n); lazy.resize(2 * n); lazyflag.resize(2 * n, false); width.resize(2 * n);
		for (int i = n; i < 2 * n; i++)node[i] = init;
		width[1] = n;
		for (int i = 2; i < 2 * n; i++) {
			width[i] = width[i >> 1] >> 1;
		}
	}
	SegTree(const vector<T>& initvec) {
		unsigned int m = initvec.size();
		while (n < m) {
			n *= 2;
			rank++;
		}
		node.resize(2 * n); lazy.resize(2 * n); lazyflag.resize(2 * n, false); width.resize(2 * n);
		for (int i = n; i < 2 * n; i++) {
			if (i - n < m)node[i] = initvec[i - n];
		}
		width[1] = n;
		for (int i = 2; i < 2 * n; i++) {
			width[i] = width[i >> 1] >> 1;
		}
	}
	virtual void update(int i, U x) {
		i += n;
		eval(i);
		updf(node[i], x, width[i]);
		if (lazyflag[i])lazyf(lazy[i], x);
		else {
			lazyflag[i] = true;
			lazy[i] = x;
		}
	}
	virtual void update(int l, int r, U x) {
		l += n; r += n;
		int nl = l, nr = r;
		while (!(nl & 1))nl >>= 1;
		while (!(nr & 1))nr >>= 1;
		nr--;
		eval(nl); eval(nr);
		while (l < r) {
			if (l & 1) {
				updf(node[l], x, width[l]);
				if (lazyflag[l])lazyf(lazy[l], x);
				else {
					lazyflag[l] = true;
					lazy[l] = x;
				}
				l++;
			}
			if (r & 1) {
				r--;
				updf(node[r], x, width[r]);
				if (lazyflag[r])lazyf(lazy[r], x);
				else {
					lazyflag[r] = true;
					lazy[r] = x;
				}
			}
			l >>= 1; r >>= 1;
		}
	}
	T operator[](const int& x) {
		eval(x + n);
		return node[x + n];
	}
	void fill(T x) {
		std::fill(all(lazyflag), false);
		std::fill(all(node), x);
	}
	void print() {
		rep(i, n)cout << operator[](i) << " ";
		cout << endl;
	}
};
class RAQ :public SegTree<lint, lint> {
	void lazyf(lint& a, const lint& b) { a += b; }
	void updf(lint& a, const lint& b, const unsigned int& width) { a += width * b; }
public:
	RAQ(int size, const lint& def = 0) :SegTree<lint, lint>(size, def) {}
	RAQ(const vector<lint>& initvec) :SegTree<lint, lint>(initvec) {}
};
class RUQ :public SegTree<lint, lint> {
	void lazyf(lint& a, const lint& b) { a = b; }
	void updf(lint& a, const lint& b, const unsigned int& width) { a = b; }
public:
	RUQ(int size, const lint& def = 0) :SegTree<lint, lint>(size, def) {}
	RUQ(const vector<lint>& initvec) :SegTree<lint, lint>(initvec) {}
};
template<typename T, typename U>
class IntervalSegTree :public SegTree<T, U> {
protected:
	using SegTree<T, U>::n;
	using SegTree<T, U>::rank;
	using SegTree<T, U>::node;
	using SegTree<T, U>::lazy;
	using SegTree<T, U>::lazyflag;
	using SegTree<T, U>::width;
	using SegTree<T, U>::eval;
	using SegTree<T, U>::lazyf;
	using SegTree<T, U>::updf;
	T nodee;
	virtual T nodef(const T&, const T&)const = 0;
public:
	IntervalSegTree(unsigned int m, T init, T nodee) :SegTree<T, U>(m, init), nodee(nodee) {}
	IntervalSegTree(T nodee, const vector<T>& initvec) :SegTree<T, U>(initvec), nodee(nodee) {}
	void update(int i, U x) {
		i += n;
		eval(i);
		updf(node[i], x, width[i]);
		if (lazyflag[i])lazyf(lazy[i], x);
		else {
			lazyflag[i] = true;
			lazy[i] = x;
		}
		while (i /= 2)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
	void update(int l, int r, U x) {
		l += n; r += n;
		int nl = l, nr = r;
		while (!(nl & 1))nl >>= 1;
		while (!(nr & 1))nr >>= 1;
		nr--;
		eval(nl); eval(nr);
		while (l < r) {
			if (l & 1) {
				updf(node[l], x, width[l]);
				if (lazyflag[l])lazyf(lazy[l], x);
				else {
					lazyflag[l] = true;
					lazy[l] = x;
				}
				l++;
			}
			if (r & 1) {
				r--;
				updf(node[r], x, width[r]);
				if (lazyflag[r])lazyf(lazy[r], x);
				else {
					lazyflag[r] = true;
					lazy[r] = x;
				}
			}
			l >>= 1; r >>= 1;
		}
		while (nl >>= 1)node[nl] = nodef(node[2 * nl], node[2 * nl + 1]);
		while (nr >>= 1)node[nr] = nodef(node[2 * nr], node[2 * nr + 1]);
	}
	T query(int l, int r) {
		l += n; r += n;
		eval(l); eval(r - 1);
		int ls = nodee, rs = nodee;
		while (l < r) {
			if (l & 1) {
				ls = nodef(ls, node[l]);
				l++;
			}
			if (r & 1) {
				r--;
				rs = nodef(node[r], rs);
			}
			l >>= 1; r >>= 1;
		}
		return nodef(ls, rs);
	}
	T queryForAll() {
		return node[1];
	}
	void print() {
		rep(i, n)cout << SegTree<T, U>::query(i) << " ";
		cout << endl;
	}
};
class RAQRSQ :public IntervalSegTree<lint, lint> {
	lint nodef(const lint& a, const lint& b)const { return a + b; }
	void lazyf(lint& a, const lint& b) { a += b; }
	void updf(lint& a, const lint& b, const unsigned int& width) { a += width * b; }
public:
	RAQRSQ(int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, 0) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
	RAQRSQ(const vector<lint>& initvec) :IntervalSegTree<lint, lint>((lint)0, initvec) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
};
class RAQRMiQ :public IntervalSegTree<lint, lint> {
	lint nodef(const lint& a, const lint& b)const { return min(a, b); }
	void lazyf(lint& a, const lint& b) { a += b; }
	void updf(lint& a, const lint& b, const unsigned int& width) { a += b; }
public:
	RAQRMiQ(int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, LINF) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
	RAQRMiQ(const vector<lint>& initvec) :IntervalSegTree<lint, lint>(LINF, initvec) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
};
class RAQRMaQ :public IntervalSegTree<lint, lint> {
	lint nodef(const lint& a, const lint& b)const { return max(a, b); }
	void lazyf(lint& a, const lint& b) { a += b; }
	void updf(lint& a, const lint& b, const unsigned int& width) { a += b; }
public:
	RAQRMaQ(unsigned int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, -LINF) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
	RAQRMaQ(const vector<lint>& initvec) :IntervalSegTree<lint, lint>(-LINF, initvec) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
};
class RUQRSQ :public IntervalSegTree<lint, lint> {
	lint nodef(const lint& a, const lint& b)const { return a + b; }
	void lazyf(lint& a, const lint& b) { a = b; }
	void updf(lint& a, const lint& b, const unsigned int& width) { a = width * b; }
public:
	RUQRSQ(int size, const int& def = 0) :IntervalSegTree<lint, lint>(size, def, 0) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
	RUQRSQ(const vector<lint>& initvec) :IntervalSegTree<lint, lint>((lint)0, initvec) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
};
class RUQRMiQ :public IntervalSegTree<lint, lint> {
	lint nodef(const int& a, const int& b)const { return min(a, b); }
	void lazyf(int& a, const int& b) { a = b; }
	void updf(int& a, const int& b, const unsigned int& width) { a = b; }
public:
	RUQRMiQ(int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, LINF) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
	RUQRMiQ(const vector<lint>& initvec) :IntervalSegTree<lint, lint>(LINF, initvec) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
};
class RUQRMaQ :public IntervalSegTree<lint, lint> {
	lint nodef(const lint& a, const lint& b)const { return max(a, b); }
	void lazyf(lint& a, const lint& b) { a = b; }
	void updf(lint& a, const lint& b, const unsigned int& width) { a = b; }
public:
	RUQRMaQ(int size, const lint& def = 0) :IntervalSegTree<lint, lint>(size, def, -LINF) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
	RUQRMaQ(const vector<lint>& initvec) :IntervalSegTree<lint, lint>(-LINF, initvec) {
		for (int i = n - 1; i > 0; i--)node[i] = nodef(node[2 * i], node[2 * i + 1]);
	}
};
int n, a[1010][1010], b[2][1010];
Vector<P> home[1010];
int main() {
	std::cin >> n;
	rep(i, n) {
		rep(j, n) {
			std::cin >> a[i][j];
			home[a[i][j]].emplace_back(i, j);
		}
	}
	lint ans = 0;
	RAQRSQ st1(n), st2(n);
	REP(i, n) {
		st1.fill(0); st2.fill(0);
		for (P j : home[i]) {
			if (j.first + j.second + 1 < n)st1.update(j.first + j.second + 1, n, 1);
			if (0 <= j.first - j.second - 1)st2.update(0, j.first - j.second, 1);
			ans += j.second;
		}
		rep(j, n - 1)st1.update(j + 1, j + 2, st1[j]);
		for (int j = n - 1; j > 0; j--)st2.update(j - 1, j, st2[j]);
		int cnt = INF;
		rep(j, n)chmin(cnt, st1[j] + st2[j]);
		ans += cnt;
	}
	std::cout << ans << std::endl;
	return 0;
}
yukicoder

結果

テストケース

ソースコード
