結果
| 問題 |
No.3292 World Map Distance
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 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 |
ソースコード
// #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;
}
/*
*/