結果
| 問題 |
No.1014 competitive fighting
|
| コンテスト | |
| ユーザー |
 kcvlex
|
| 提出日時 | 2020-03-20 23:01:07 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,799 bytes |
| コンパイル時間 | 2,254 ms |
| コンパイル使用メモリ | 200,468 KB |
| 実行使用メモリ | 76,464 KB |
| 最終ジャッジ日時 | 2024-12-15 07:59:59 |
| 合計ジャッジ時間 | 10,875 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 WA * 22 |
ソースコード
#include <bits/stdc++.h>
#define ALL(v) std::begin(v), std::end(v)
#define ALLR(v) std::rbegin(v), std::rend(v)
using ll = std::int64_t;
using ull = std::uint64_t;
using pii = std::pair<int, int>;
using tii = std::tuple<int, int, int>;
using pll = std::pair<ll, ll>;
using tll = std::tuple<ll, ll, ll>;
template <typename T> using vec = std::vector<T>;
template <typename T> using vvec = vec<vec<T>>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, std::size_t s, Tail... tail) { auto v = std::move(make_v(init, tail...)); return vec<decltype(v)>(s, v); }
template <typename T, std::size_t Head, std::size_t ...Tail> struct multi_dem_array { using type = std::array<typename multi_dem_array<T, Tail...>::type, Head>; };
template <typename T, std::size_t Head> struct multi_dem_array<T, Head> { using type = std::array<T, Head>; };
template <typename T, std::size_t ...Args> using mdarray = typename multi_dem_array<T, Args...>::type;
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
namespace segtree {
template <typename T>
struct SegmentTree {
using Merge = std::function<T(T, T)>;
vec<T> nodes;
Merge merge_f;
T id_ele;
SegmentTree(const vec<T> &init_v, Merge merge_f, T id_ele)
: nodes(ceil_pow2(init_v.size()) * 2 - 1, id_ele), merge_f(merge_f), id_ele(id_ele)
{
ssize_t s = size();
for (ssize_t i = 0; i < init_v.size(); i++) nodes[i + s - 1] = init_v[i];
for (ssize_t i = s - 2; 0 <= i; i--) nodes[i] = get_merged(i);
}
size_t size() const {
return (nodes.size() + 1) / 2;
}
const T& operator [](ll idx) const {
return nodes[idx + size() - 1];
}
T get_query(ll ql, ll qr, ll nl, ll nr, ll nidx) const {
if (nr <= ql || qr <= nl) return id_ele;
if (ql <= nl && nr <= qr) return nodes[nidx];
ll mid = (nl + nr) / 2;
ll lidx, ridx;
std::tie(lidx, ridx) = get_children_idx(nidx);
auto lv = get_query(ql, qr, nl, mid, lidx);
auto rv = get_query(ql, qr, mid, nr, ridx);
return merge_f(lv, rv);
}
T get_query(ll ql, ll qr) const {
return get_query(ql, qr, 0, size(), 0);
}
void update_query(ll idx, T val) {
idx += size() - 1;
nodes[idx] = val;
while (idx) {
ll pidx = (idx - 1) / 2;
nodes[pidx] = get_merged(pidx);
idx = pidx;
}
}
// FIXME : test
T lower_bound(ll idx, std::function<bool(T)> check, T sum) const {
if (size() - 1 <= idx) return idx - (size() - 1);
ll lidx, ridx;
std::tie(lidx, ridx) = get_children_idx(idx);
auto lv = merge_f(sum, nodes[lidx]);
if (check(lv)) return lower_bound(lidx, check, sum);
else return lower_bound(ridx, check, lv);
}
T lower_bound(std::function<bool(T)> check) const {
return lower_bound(0, check, id_ele);
}
private:
ssize_t ceil_pow2(ssize_t s) {
ssize_t ret = 1;
while (ret <= s) ret *= 2;
return ret;
}
pll get_children_idx(ll idx) const {
return pll(2 * idx + 1, 2 * idx + 2);
}
T get_merged(ll idx) const {
ll a, b;
std::tie(a, b) = get_children_idx(idx);
return merge_f(nodes[a], nodes[b]);
}
};
}
namespace graph {
using Node = ll;
using Weight = ll;
using Edge = std::pair<Node, Weight>;
template <bool Directed>
struct Graph : public vvec<Edge> {
using vvec<Edge>::vvec;
void add_edge(Node f, Node t, Weight w = 1) {
(*this)[f].emplace_back(t, w);
if (!Directed) (*this)[t].emplace_back(f, w);
}
Graph<Directed> build_inv() const {
Graph<Directed> ret(this->size());
for (Node i = 0; i < this->size(); i++) {
for (const Edge &e : (*this)[i]) {
Node j;
Weight w;
std::tie(j, w) = e;
if (!Directed && j < i) continue;
ret.add_edge(j, i, w);
}
}
return ret;
}
};
}
const std::size_t SIZE = 1e5 + 10;
mdarray<pll, 32, SIZE> dp;
bool limited[SIZE];
ll maxv[SIZE];
struct Compress {
vec<ll> a;
Compress(vec<ll> a_) : a(std::move(a_)) {
std::sort(ALL(a));
auto ite = std::unique(ALL(a));
a.erase(ite, a.end());
}
ll get_id(ll e) {
return std::distance(a.begin(),
std::lower_bound(ALL(a), e));
}
};
const ll inf = 5e15;
int main() {
ll n;
std::cin >> n;
vec<tll> abc(n);
vec<ll> av(n);
for (ll i = 0; i < n; i++) {
ll a, b, c;
std::cin >> a >> b >> c;
abc[i] = tll(a, b, c);
av[i] = a;
}
Compress cmp(av);
tll err(-inf, 0, -1);
vec<tll> init_v(av.size());
vvec<tll> bc_lis(av.size());
for (ll i = 0; i < n; i++) {
ll a, b, c;
std::tie(a, b, c) = abc[i];
ll idx = cmp.get_id(a);
bc_lis[idx].emplace_back(b - c, b, i);
}
for (auto &&v : bc_lis) {
v.emplace_back(err);
std::sort(ALLR(v));
}
for (ll i = 0; i < init_v.size(); i++) init_v[i] = bc_lis[i][0];
segtree::SegmentTree<tll> seg(init_v, [](tll a, tll b) { return std::max(a, b); }, err);
vec<ll> nxts(n, -1);
for (ll i = 0; i < n; i++) {
ll a, b, c;
std::tie(a, b, c) = abc[i];
ll idx = cmp.get_id(a);
bool changed = false;
if (std::get<2>(bc_lis[idx][0]) == i) {
changed = true;
seg.update_query(idx, bc_lis[idx][1]);
}
auto ite = std::upper_bound(ALL(cmp.a), b - c);
auto r = std::distance(cmp.a.begin(), ite);
if (0 < r) {
auto qr = seg.get_query(0, r);
nxts[i] = std::get<2>(qr);
}
if (changed) seg.update_query(idx, bc_lis[idx][0]);
}
for (ll i = 0; i < n; i++) {
ll b;
std::tie(std::ignore, b, std::ignore) = abc[i];
if (nxts[i] == -1) {
dp[0][i] = pll(-1, b);
limited[i] = true;
maxv[i] = b;
} else {
dp[0][i] = pll(nxts[i], b);
}
}
for (ll i = 0; i < 32 - 1; i++) {
for (ll j = 0; j < n; j++) {
ll cur, sum;
std::tie(cur, sum) = dp[i][j];
if (cur == -1) {
maxv[j] = sum;
limited[j] = true;
dp[i + 1][j] = dp[i][j];
continue;
}
ll nxt, addv;
std::tie(nxt, addv) = dp[i][cur];
sum += addv;
dp[i + 1][j] = pll(nxt, sum);
}
}
for (ll i = 0; i < n; i++) {
if (!limited[i]) std::cout << "BAN";
else std::cout << maxv[i];
std::cout << '\n';
}
return 0;
}