結果
| 問題 | No.1014 competitive fighting |
| ユーザー |
 kcvlex
|
| 提出日時 | 2020-03-20 22:55:06 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,927 bytes |
| コンパイル時間 | 2,479 ms |
| コンパイル使用メモリ | 198,420 KB |
| 実行使用メモリ | 72,448 KB |
| 最終ジャッジ日時 | 2024-05-08 23:45:46 |
| 合計ジャッジ時間 | 14,280 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | WA | - |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | RE | - |
| testcase_05 | AC | 274 ms
72,448 KB |
| testcase_06 | WA | - |
| testcase_07 | AC | 261 ms
72,448 KB |
| testcase_08 | AC | 264 ms
72,448 KB |
| testcase_09 | AC | 262 ms
72,448 KB |
| testcase_10 | AC | 113 ms
70,516 KB |
| testcase_11 | AC | 115 ms
71,536 KB |
| testcase_12 | AC | 265 ms
72,448 KB |
| testcase_13 | AC | 114 ms
35,968 KB |
| testcase_14 | AC | 103 ms
33,664 KB |
| testcase_15 | AC | 125 ms
39,040 KB |
| testcase_16 | AC | 6 ms
5,376 KB |
| testcase_17 | AC | 42 ms
16,256 KB |
| testcase_18 | AC | 213 ms
60,672 KB |
| testcase_19 | AC | 256 ms
70,784 KB |
| testcase_20 | AC | 83 ms
27,776 KB |
| testcase_21 | AC | 192 ms
55,424 KB |
| testcase_22 | AC | 151 ms
45,056 KB |
| testcase_23 | AC | 55 ms
20,224 KB |
| testcase_24 | WA | - |
| testcase_25 | AC | 14 ms
7,424 KB |
| testcase_26 | AC | 187 ms
54,784 KB |
| testcase_27 | AC | 41 ms
16,256 KB |
| testcase_28 | AC | 47 ms
17,792 KB |
| testcase_29 | AC | 3 ms
5,376 KB |
| testcase_30 | AC | 258 ms
70,144 KB |
| testcase_31 | AC | 203 ms
57,088 KB |
| testcase_32 | AC | 3 ms
5,376 KB |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | AC | 262 ms
72,448 KB |
ソースコード
#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);
pll err(-inf, -inf);
vec<pll> init_v(av.size());
vvec<pll> 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, i);
}
for (auto &&v : bc_lis) {
v.emplace_back(-inf, -inf);
std::sort(ALLR(v));
}
for (ll i = 0; i < init_v.size(); i++) init_v[i] = bc_lis[i][0];
auto merge = [](pll p, pll q) {
ll a, b, c, d;
std::tie(a, b) = p;
std::tie(c, d) = q;
if (a > c) return p;
else return q;
};
segtree::SegmentTree<pll> seg(init_v, merge, 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 (bc_lis[idx][0].second == 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] = qr.second;
}
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;
}