結果
| 問題 |
No.3214 small square
|
| ユーザー |
 dp_ijk
|
| 提出日時 | 2025-07-25 22:49:21 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,710 bytes |
| コンパイル時間 | 2,258 ms |
| コンパイル使用メモリ | 183,276 KB |
| 実行使用メモリ | 288,664 KB |
| 最終ジャッジ日時 | 2025-07-25 22:49:29 |
| 合計ジャッジ時間 | 7,597 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 TLE * 1 -- * 29 |
ソースコード
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cmath>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(15);
std::cerr << std::fixed << std::setprecision(8);
}
};
IOSetup iosetup;
using int128_t = __int128;
using uint128_t = unsigned __int128;
template <typename T>
constexpr auto rep_iota_impl(T start, T stop) noexcept {
return std::views::iota(start, (start < stop ? stop : start));
}
template <typename T = int64_t>
constexpr auto rep_impl(auto start, auto stop) noexcept {
return rep_iota_impl<T>(start, stop);
}
template <typename T = int64_t>
constexpr auto rep_impl(auto stop) noexcept {
return rep_iota_impl<T>(0, stop);
}
template <class... Ts>
inline void read(Ts&... ts) {
(std::cin >> ... >> ts);
}
template <class T, class U>
inline bool chmax(T& a, U b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T, class U>
inline bool chmin(T& a, U b) {
if (a > b) {
a = b;
return true;
}
return false;
}
using std::vector;
template <typename X>
struct MAdd {
using ll = int64_t;
using T = X;
static constexpr T op(const T& x, const T& y) noexcept { return x + y; }
static constexpr T inverse(const T& x) noexcept { return -x; }
static constexpr T power(const T& x, ll n) noexcept { return T{x} * n; }
static constexpr T unit() noexcept { return T{}; }
static constexpr bool is_unit(const T& x) noexcept { return x == T{}; }
static constexpr bool commutative = 1;
static constexpr bool invertible = 1;
};
template <typename T>
void put(const T& t) {
std::cout << t;
}
template <typename... Ts>
void print(const Ts&... ts) {
put(ts...);
std::cout << "\n";
}
using std::cin;
using std::cout;
using std::map;
using std::pair;
using std::set;
using std::string;
using std::tuple;
using std::vector;
using ll = int64_t;
template <typename MX_, typename MA_, auto operate, auto default_factory>
struct DynamicLazySegTree {
public:
using ll = int64_t;
using MX = MX_;
using MA = MA_;
using X = typename MX::T;
using A = typename MA::T;
using value_type = typename MX::T;
static_assert(std::is_invocable_v<decltype(operate), X, A, ll>);
struct Node;
using Tree = Node*;
struct Node {
X val;
A lazy;
Tree left, right;
Node()
: val(MX::unit()),
lazy(MA::unit()),
left(nullptr),
right(nullptr) {}
};
auto _new(ll nL, ll nR) {
auto t = new Node();
t->val = default_factory(nL, nR);
return t;
}
inline void _del(Tree t) { delete t; }
void _delete_subtree(Tree t) {
if (!t) return;
_delete_subtree(t->left);
_delete_subtree(t->right);
_del(t);
}
void clear() {
_delete_subtree(root);
root = nullptr;
}
Tree root;
const ll maxlen;
DynamicLazySegTree() = default;
explicit DynamicLazySegTree(ll maxlen_)
: root(_new(0, maxlen_)),
maxlen(maxlen_) {
assert(maxlen_ >= 0);
}
private:
void apply_subtree(Tree t, const A& a, const ll nL, const ll nR) const {
assert(nL < nR);
t->val = operate(t->val, a, nR - nL);
t->lazy = MA::op(t->lazy, a);
}
void push_lazy(Tree t, ll nL, ll nR) {
assert(nR - nL >= 2);
if (nR - nL == 1) return;
assert(t);
if (t->lazy == MA::unit()) return;
ll m = std::midpoint(nL, nR);
if (!t->left) t->left = _new(nL, m);
if (!t->right) t->right = _new(m, nR);
apply_subtree(t->left, t->lazy, nL, m);
apply_subtree(t->right, t->lazy, m, nR);
t->lazy = MA::unit();
}
void update(Tree t, ll nL, ll nR) {
assert(t);
assert(nR - nL >= 2);
if (nR - nL == 1) return;
ll m = std::midpoint(nL, nR);
X vL = t->left ? t->left->val : default_factory(nL, m);
X vR = t->right ? t->right->val : default_factory(m, nR);
t->val = MX::op(vL, vR);
}
public:
X fold(ll l, ll r) { return _fold(l, r, MA::unit(), root, 0, maxlen); }
X fold_all() { return fold(0, maxlen); }
X _fold(ll l, ll r, const A lazy, Tree t, const ll nL, const ll nR) {
chmax(l, nL);
chmin(r, nR);
if (not(l < r)) return MX::unit();
if (!t) { return operate(default_factory(l, r), lazy, r - l); }
if (l == nL && r == nR) { return operate(t->val, lazy, r - l); }
ll m = std::midpoint(nL, nR);
A nlazy = MA::op(t->lazy, lazy);
X vL = _fold(l, r, nlazy, t->left, nL, m);
X vR = _fold(l, r, nlazy, t->right, m, nR);
return MX::op(vL, vR);
}
void apply(const ll l, const ll r, const A& a) { _apply(l, r, a, root, 0, maxlen); }
Tree _apply(ll l, ll r, const A a, Tree t, const ll nL, const ll nR) {
if (a == MA::unit()) return t;
if (!t) t = _new(nL, nR);
chmax(l, nL);
chmin(r, nR);
if (not(l < r)) return t;
if (l == nL && r == nR) {
apply_subtree(t, a, nL, nR);
return t;
}
push_lazy(t, nL, nR);
ll m = std::midpoint(nL, nR);
t->left = _apply(l, r, a, t->left, nL, m);
t->right = _apply(l, r, a, t->right, m, nR);
update(t, nL, nR);
return t;
}
void set(const ll i, const X& x) {
assert(0 <= i && i < maxlen);
root = _set(i, x, root, 0, maxlen);
}
Tree _set(const ll i, const X& x, Tree t, const ll nL, const ll nR) {
if (nR - nL == 1) {
t->val = x;
t->lazy = MA::unit();
return t;
}
push_lazy(t, nL, nR);
ll m = std::midpoint(nL, nR);
if (!t->left) t->left = _new(nL, m);
if (!t->right) t->right = _new(m, nR);
if (i < m) {
t->left = _set(i, x, t->left, nL, m);
} else {
t->right = _set(i, x, t->right, m, nR);
}
update(t, nL, nR);
return t;
}
X operator[](ll k) const { return fold(k, k + 1); }
X get(ll k) const { return fold(k, k + 1); }
};
constexpr int64_t INF = 23e17;
template <typename X, X INF>
struct MMax {
using T = X;
static constexpr T op(T x, T y) { return (x < y) ? y : x; }
static constexpr T unit() { return -INF; }
static constexpr bool is_unit(const T& x) { return x == -INF; }
static constexpr bool commutative = true;
static constexpr bool idempotent = true;
};
ll operate(ll M, ll a, [[maybe_unused]] ll sz) { return M + a; }
ll default_factory(ll l, ll r) { return 0; }
struct Point {
ll x, y, v;
};
ll resolve(ll N, ll P, ll Q, vector<Point> XYV) {
ll minY = INF;
for (const auto i : rep_impl((N))) {
auto [x, y, v] = XYV[i];
chmin(minY, y);
}
for (const auto i : rep_impl((N))) {
auto [x, y, v] = XYV[i];
XYV[i] = {x, y - minY + (Q - 1), v};
}
map<ll, vector<Point>> todo;
for (const auto i : rep_impl((N))) {
auto [x, y, v] = XYV[i];
todo[x].push_back({x, y, v});
}
set<ll> T;
for (auto& [x, _] : todo) {
T.insert(x - (P - 1));
T.insert(x + 1);
}
auto seg = DynamicLazySegTree<MMax<ll, INF>, MAdd<ll>, operate, default_factory>(1e10);
ll res = 0;
for (auto t : T) {
for (auto [x, y, v] : todo[t + (P - 1)]) {
assert(0 <= y - (Q - 1));
seg.apply(y - (Q - 1), y + 1, v);
}
for (auto [x, y, v] : todo[t - 1]) {
assert(0 <= y - (Q - 1));
seg.apply(y - (Q - 1), y + 1, -v);
}
ll nres = seg.fold_all();
chmax(res, nres);
}
seg.clear();
return res;
}
int main() {
int64_t N, A;
read(N, A);
vector<Point> XYV(N);
for (const auto i : rep_impl((N))) {
int64_t x, y, v;
read(x, y, v);
XYV[i] = {x, y, v};
}
ll res = 0;
for (const auto P : rep_impl((A), (A + 2)))
for (const auto Q : rep_impl((A), (A + 2)))
chmax(res, resolve(N, P, Q, XYV));
print(res);
}