結果

問題 No.3292 World Map Distance
ユーザー Aeren
提出日時 2025-10-03 22:41:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,932 bytes
コンパイル時間 3,462 ms
コンパイル使用メモリ 292,512 KB
実行使用メモリ 814,492 KB
最終ジャッジ日時 2025-10-03 22:41:12
合計ジャッジ時間 5,623 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 MLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

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;
}

template<class T>
struct arithmetic_sequence_update_processor{
#ifdef LOCAL
	#define ASSERT(x) assert(x)
#else
	#define ASSERT(x) 42
#endif
	bool reversed;
	int n, ptr;
	vector<T> data, res;
	arithmetic_sequence_update_processor(int n, bool reversed = false): reversed(reversed), n(n), ptr(0), data(n + 2, T{}){
		ASSERT(n >= 0);
	}
	// O(n)
	void clear(){
		ptr = 0;
		fill(data.begin(), data.end(), T{});
	}
	// Add start, start + step, start + step * 2, ... on [l, r)
	// l must be equal or greater than the largest index which query() has been called over if reverse = false
	// Otherwise, r must be equal or less than the smallest index which query() has been called over plus one
	// If ALLOW_OUT_OF_RANGE, every update outside of [ptr, n) range will be ignored.
	// O(1)
	template<bool ALLOW_OUT_OF_RANGE = false>
	void update(int l, int r, T start, T step = T{}){
		if(reversed) tie(l, r, start, step) = tuple{n - r, n - l, start + (r - l - 1) * step, -step};
		ASSERT(l <= r);
		if constexpr(ALLOW_OUT_OF_RANGE){
			if(n <= l || r <= ptr) return;
			if(l < ptr){
				start += (ptr - l) * step;
				l = ptr;
			}
			r = min(n, r);
		}
		ASSERT(ptr <= l && r <= n);
		if(l == r) return;
		data[l] += start;
		data[l + 1] -= start - step;
		data[r] -= start + (r - l) * step;
		data[r + 1] += start + (r - l - 1) * step;
	}
	// Add rev_start + (r - l - 1) * rev_step, rev_start + (r - l - 2) * rev_step, ... on [l, r)
	// l must be equal or greater than the largest index which query() has been called over if reverse = false
	// Otherwise, r must be equal or less than the smallest index which query() has been called over plus one
	// If ALLOW_OUT_OF_RANGE, every update outside of [ptr, n) range will be ignored.
	// O(1)
	template<bool ALLOW_OUT_OF_RANGE = false>
	void update_reverse(int l, int r, T rev_start, T rev_step = T{}){
		update<ALLOW_OUT_OF_RANGE>(l, r, rev_start + (r - l - 1) * rev_step, -rev_step);
	}
	// Add x to position p
	// p must be equal or greater than the largest index which query() has been called over
	// O(1)
	void update(int p, T x){
		if(reversed) p = n - 1 - p;
		ASSERT(ptr <= p && p < n);
		data[p] += x;
		data[p + 1] -= 2 * x;
		data[p + 2] += x;
	}
	// O(max(1, p - ptr))
	T query(int p){
		if(reversed) p = n - 1 - p;
		ASSERT(0 <= p && p < n);
		for(; ptr < p; ++ ptr){
			data[ptr + 1] += data[ptr];
			if(ptr >= 1) data[ptr] += data[ptr - 1];
		}
		return p == ptr ? data[p] + (p >= 1 ? data[p - 1] : T{}) : data[p];
	}
	// O(n)
	const vector<T> &snapshot(){
		res.resize(n + 1);
		copy(data.begin(), data.end() - 1, res.begin());
		for(auto i = ptr; i < n; ++ i){
			res[i + 1] += res[i];
			if(1 <= i) res[i] += res[i - 1];
		}
		res.pop_back();
		if(reversed) reverse(res.begin(), res.end());
		return res;
	}
#undef ASSERT
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n, nr, nc;
	cin >> n >> nr >> nc;
	vector<int> 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; ++ _){
		arithmetic_sequence_update_processor<long long> processor(2 * nr);
		for(auto x: rs){
			processor.update(x, x + nr / 2 + 1, 0, 1);
			processor.update_reverse(x + nr / 2 + 1, x + nr, 1, 1);
		}
		processor.snapshot();
		vector<long long> cur(nr);
		for(auto x = 0; x < 2 * nr; ++ x){
			cur[x % nr] += processor.res[x];
		}
		res += ranges::max(cur);
		swap(nr, nc);
		swap(rs, cs);
	}
	cout << res << "\n";
	return 0;
}

/*

*/
0