結果

問題 No.3292 World Map Distance
ユーザー Aeren
提出日時 2025-10-03 22:57:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,252 ms / 3,000 ms
コード長 12,226 bytes
コンパイル時間 3,542 ms
コンパイル使用メモリ 293,328 KB
実行使用メモリ 43,904 KB
最終ジャッジ日時 2025-10-03 22:57:29
合計ジャッジ時間 15,558 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
using namespace numbers;
#ifdef LOCAL
	#include "Debug.h"
#else
	#define debug_endl() 42
	#define debug(...) 42
	#define debug2(...) 42
	#define debug_bin(...) 42
#endif
// Returns the largest integer k with x >= k * y
template<class T, class U> U floor_div(T x, U y){
	assert(y > 0);
	return x / y - (x % y < 0);
}
// Returns the smallest integer k with x <= k * y
template<class T, class U> U ceil_div(T x, U y){
	assert(y > 0);
	return x / y + (x % y > 0);
}
template<class T> T &ctmin(T &x){ return x; }
template<class T, class Head, class ...Tail> T &ctmin(T &x, const Head &h, const Tail &... t){ return ctmin(x = min<T>(x, h), t...); }
template<class T> T &ctmax(T &x){ return x; }
template<class T, class Head, class ...Tail> T &ctmax(T &x, const Head &h, const Tail &... t){ return ctmax(x = max<T>(x, h), t...); }

// std::chunk_by cuz AtCoder is stuck on 3 years old gcc
vector<vector<int>> chunk_by(auto data, auto eq){
	vector<vector<int>> chunks;
	for(auto l = data.begin(); l != data.end(); ){
		auto r = next(l);
		vector<int> chunk{*l};
		while(r != data.end() && eq(*prev(r), *r)){
			chunk.push_back(*r);
			r = next(r);
		}
		chunks.push_back(chunk);
		l = r;
	}
	return chunks;
}

// Keeps track of piecewise linear function over real numbers x with left_boundary <= x < right_boundary
// Each connected component must be left-closed and right-open
template<class Key_t, class Value_t>
struct piecewise_linear_function_container{
#ifdef LOCAL
	#define ASSERT(x) assert(x)
#else
	#define ASSERT(x) 42
#endif
	Key_t left_boundary, right_boundary;
	Value_t initial_value, initial_slope;
	map<Key_t, Value_t> first_derivative;
	map<Key_t, Value_t> second_derivative;
	void _update_1(Key_t x, Value_t value_dif){
		ASSERT(left_boundary <= x && x < right_boundary);
		if(value_dif == Value_t{0}) return;
		if(x == left_boundary) initial_value += value_dif;
		else if((first_derivative[x] += value_dif) == 0) first_derivative.erase(x);
	}
	void _update_2(Key_t x, Value_t slope_dif){
		ASSERT(left_boundary <= x && x < right_boundary);
		if(slope_dif == Value_t{0}) return;
		if(x == left_boundary) initial_slope += slope_dif;
		else if((second_derivative[x] += slope_dif) == 0) second_derivative.erase(x);
	}
	piecewise_linear_function_container(
		Key_t left_boundary = numeric_limits<Key_t>::min(),
		Key_t right_boundary = numeric_limits<Key_t>::max(),
		Value_t initial_value = 0,
		Value_t initial_slope = 0
	): left_boundary(left_boundary), right_boundary(right_boundary), initial_value(initial_value), initial_slope(initial_slope){
		ASSERT(left_boundary < right_boundary);
	}
	void clear(
		Key_t left_boundary = numeric_limits<Key_t>::min(),
		Key_t right_boundary = numeric_limits<Key_t>::max(),
		Value_t initial_value = 0,
		Value_t initial_slope = 0
	){
		ASSERT(left_boundary < right_boundary);
		this->left_boundary = left_boundary;
		this->right_boundary = right_boundary;
		this->initial_value = initial_value;
		this->initial_slope = initial_slope;
		first_derivative.clear();
		second_derivative.clear();
	}
	// Add value + slope * (x - l) at x for each l <= x < r
	void add(Key_t l, Key_t r, Value_t value, Value_t slope){
		ASSERT(l <= r);
		r = clamp(r, left_boundary, right_boundary);
		if(l < left_boundary){
			value += slope * (left_boundary - l);
			l = left_boundary;
		}
		l = min(l, right_boundary);
		if(l == r) return;
		_update_1(l, value);
		_update_2(l, slope);
		if(r < right_boundary){
			_update_1(r, -value - slope * (r - l));
			_update_2(r, -slope);
		}
	}
	// Add value_reversed + slope_reversed * (r - x) at x for each l <= x < r
	void add_reversed(Key_t l, Key_t r, Value_t value_reversed, Value_t slope_reversed){
		add(l, r, value_reversed + slope_reversed * (r - l), -slope_reversed);
	}
	// Add connected piecewise line, left-closed and right-open, connecting the given points in order
	void add_piecewise_line(vector<pair<Key_t, Value_t>> piecewise_line){
		for(auto i = 0; i + 1 < (int)piecewise_line.size(); ++ i) ASSERT(piecewise_line[i].first < piecewise_line[i + 1].first);
		if((int)piecewise_line.size() < 2 || piecewise_line.back().first <= left_boundary || right_boundary <= piecewise_line.front().first) return;
		int head = 0;
		while(head + 1 < (int)piecewise_line.size() && piecewise_line[head + 1].first <= left_boundary) ++ head;
		piecewise_line.erase(piecewise_line.begin(), piecewise_line.begin() + head);
		if(piecewise_line[0].first < left_boundary){
			Value_t slope = (piecewise_line[1].second - piecewise_line[0].second) / (piecewise_line[1].first - piecewise_line[0].first);
			piecewise_line[0] = {left_boundary, piecewise_line[0].second + slope * (left_boundary - piecewise_line[0].first)};
		}
		while((int)piecewise_line.size() >= 2 && piecewise_line.end()[-2].first >= right_boundary) piecewise_line.pop_back();
		if(piecewise_line.end()[-1].first > right_boundary){
			Value_t slope = (piecewise_line.end()[-2].second - piecewise_line.end()[-1].second) / (piecewise_line.end()[-2].first - piecewise_line.end()[-1].first);
			piecewise_line.end()[-1] = {right_boundary, piecewise_line.end()[-1].second + slope * (right_boundary - piecewise_line.end()[-1].first)};
		}
		_update_1(piecewise_line.front().first, piecewise_line.front().second);
		Value_t slope = 0;
		for(auto i = 0; i + 1 < (int)piecewise_line.size(); ++ i){
			Value_t next_slope = (piecewise_line[i + 1].second - piecewise_line[i].second) / (piecewise_line[i + 1].first - piecewise_line[i].first);
			_update_2(piecewise_line[i].first, next_slope - slope);
			slope = next_slope;
		}
		if(piecewise_line.back().first < right_boundary){
			_update_1(piecewise_line.back().first, -piecewise_line.back().second);
			_update_2(piecewise_line.back().first, -slope);
		}
	}
	void add_piecewise_line(int n, auto f){
		ASSERT(n >= 0);
		vector<pair<Key_t, Value_t>> piecewise_line(n);
		for(auto i = 0; i < n; ++ i) piecewise_line[i] = f(i);
		add_piecewise_line(piecewise_line);
	}
	void set_left_boundary(Key_t new_left_boundary, auto process){
		ASSERT(left_boundary <= new_left_boundary && new_left_boundary < right_boundary);
		if(new_left_boundary == left_boundary) return;
		Key_t pos = left_boundary;
		Value_t value = initial_value;
		Value_t slope = initial_slope;
		auto it1 = first_derivative.begin();
		auto it2 = second_derivative.begin();
		for(; it2 != second_derivative.end() && it2->first <= new_left_boundary; it2 = second_derivative.erase(it2)){
			for(; it1 != first_derivative.end() && it1->first <= it2->first; it1 = first_derivative.erase(it1)){
				process(pos, it1->first, value, slope);
				value += it1->second + slope * (it1->first - pos);
				pos = it1->first;
			}
			if(pos < it2->first) process(pos, it2->first, value, slope);
			value += slope * (it2->first - pos);
			slope += it2->second;
			pos = it2->first;
		}
		for(; it1 != first_derivative.end() && it1->first <= new_left_boundary; it1 = first_derivative.erase(it1)){
			process(pos, it1->first, value, slope);
			value += it1->second + slope * (it1->first - pos);
			pos = it1->first;
		}
		if(pos < new_left_boundary){
			process(pos, new_left_boundary, value, slope);
			value += slope * (new_left_boundary - pos);
			pos = new_left_boundary;
		}
		left_boundary = new_left_boundary;
		initial_value = value;
		initial_slope = slope;
	}
	void set_left_boundary(Key_t new_left_boundary){
		set_left_boundary(new_left_boundary, [&](Key_t, Key_t, Value_t, Value_t){  });
	}
	// Return {left, right, value, slope} of the leftmost line segment
	tuple<Key_t, Key_t, Value_t, Value_t> eval_left_line_segment() const{
		Key_t right = right_boundary;
		if(!first_derivative.empty() && (second_derivative.empty() || first_derivative.begin()->first <= second_derivative.begin()->first)) right = first_derivative.begin()->first;
		else if(!second_derivative.empty()) right = second_derivative.begin()->first;
		return {left_boundary, right, initial_value, initial_slope};
	}
	// Split [l, r) into maximal intervals [p_0=l, p_1), [p_1, p_2), ..., [p_{k-2}, p_{k-1}=r)
	// such that p_i < p_{i+1} and [p_i, p_{i+1}) is a line segment
	// Call process_while(p_i, p_{i+1}, value at p_i, slope) for each such intervals in increasing order of i
	void iterate_all_line_segments(Key_t l, Key_t r, auto process_while) const{
		ASSERT(left_boundary <= l && l <= r && r <= right_boundary);
		if(l == r) return;
		Key_t pos = left_boundary;
		Value_t value = initial_value;
		Value_t slope = initial_slope;
		auto it1 = first_derivative.begin();
		auto it2 = second_derivative.begin();
		for(; it2 != second_derivative.end() && it2->first <= l; ++ it2){
			for(; it1 != first_derivative.end() && it1->first <= it2->first; ++ it1) value += it1->second;
			value += slope * (it2->first - pos);
			slope += it2->second;
			pos = it2->first;
		}
		for(; it1 != first_derivative.end() && it1->first <= l; ++ it1) value += it1->second;
		value += slope * (l - pos);
		pos = l;
		for(; it2 != second_derivative.end() && it2->first < r; ++ it2){
			for(; it1 != first_derivative.end() && it1->first <= it2->first; ++ it1){
				if(!process_while(pos, it1->first, value, slope)) return;
				value += it1->second + slope * (it1->first - pos);
				pos = it1->first;
			}
			if(pos < it2->first) if(!process_while(pos, it2->first, value, slope)) return;
			value += slope * (it2->first - pos);
			slope += it2->second;
			pos = it2->first;
		}
		for(; it1 != first_derivative.end() && it1->first < r; ++ it1){
			if(!process_while(pos, it1->first, value, slope)) return;
			value += it1->second + slope * (it1->first - pos);
			pos = it1->first;
		}
		process_while(pos, r, value, slope);
	}
	friend ostream &operator<<(ostream &out, const piecewise_linear_function_container &plfc){
		out << "\n";
		bool first = true;
		bool from_found = false;
		Key_t from = plfc.left_boundary;
		Key_t to = plfc.left_boundary;
		plfc.iterate_all_line_segments(plfc.left_boundary, plfc.right_boundary, [&](Key_t l, Key_t r, Value_t value, Value_t slope){
			if(first) out << "(" << l << ", " << value << ")", first = false;
			out << "<" << slope << ">(" << r << ", " << value + slope * (r - l) << ")";
			if(value || slope){
				if(!from_found){
					from_found = true;
					from = l;
				}
				to = r;
			}
			return true;
		});
		out << "\n";
		vector<Value_t> a(to - from + 1);
		plfc.iterate_all_line_segments(plfc.left_boundary, plfc.right_boundary, [&](Key_t l, Key_t r, Value_t value, Value_t slope){
			if(from <= l && r <= to) for(auto i = l; i <= r; ++ i) a[i - from] = value + slope * (i - l);
			return true;
		});
		out << "[" << from << " ~ " << to << "]: {";
		for(auto i = 0; i <= to - from; ++ i){
			out << a[i];
			if(i + 1 <= to - from) out << ", ";
		}
		return out << "}";
	}
#undef ASSERT
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n;
	long long nr, nc;
	cin >> n >> nr >> nc;
	vector<long long> rs(n), cs(n);
	for(auto i = 0; i < n; ++ i){
		cin >> rs[i] >> cs[i], -- rs[i], -- cs[i];
	}
	long long res = 0;
	for(auto _ = 0; _ < 2; ++ _){
		piecewise_linear_function_container<long long, long long> container(0, nr - 1);
		for(auto x: rs){
			if(nr & 1){
				container.add_piecewise_line(vector<pair<long long, long long>>{
					{x - nr / 2 - nr, nr / 2},
					{x - nr, 0},
					{x + nr / 2 - nr, nr / 2},

					{x - nr / 2, nr / 2},
					{x, 0},
					{x + nr / 2, nr / 2},

					{x - nr / 2 + nr, nr / 2},
					{x + nr, 0},
					{x + nr / 2 + nr, nr / 2},
				});
			}
			else{
				container.add_piecewise_line(vector<pair<long long, long long>>{
					{x - nr / 2 * 3, nr / 2},
					{x - nr, 0},
					{x - nr / 2, nr / 2},
					{x, 0},
					{x + nr / 2, nr / 2},
					{x + nr, 0},
					{x + nr / 2 * 3, nr / 2},
				});
			}
		}
		long long cur = 0;
		container.iterate_all_line_segments(0, nr - 1, [&](long long l, long long r, long long x, long long slope){
			ctmax(cur, max(x, x + slope * (r - l)));
			return true;
		});
		res += cur;
		swap(nr, nc);
		swap(rs, cs);
	}
	cout << res << "\n";
	return 0;
}

/*

*/
0