結果
| 問題 |
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 |
ソースコード
// #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;
}
/*
*/