結果
問題 | No.1014 competitive fighting |
ユーザー | 👑 はまやんはまやん |
提出日時 | 2020-03-21 13:57:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 3,408 bytes |
コンパイル時間 | 2,525 ms |
コンパイル使用メモリ | 220,276 KB |
実行使用メモリ | 43,016 KB |
最終ジャッジ日時 | 2023-09-21 19:24:52 |
合計ジャッジ時間 | 9,118 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
7,580 KB |
testcase_01 | AC | 4 ms
7,524 KB |
testcase_02 | AC | 4 ms
7,584 KB |
testcase_03 | AC | 3 ms
7,576 KB |
testcase_04 | AC | 4 ms
7,624 KB |
testcase_05 | AC | 128 ms
26,696 KB |
testcase_06 | AC | 130 ms
26,576 KB |
testcase_07 | AC | 129 ms
26,628 KB |
testcase_08 | AC | 128 ms
26,552 KB |
testcase_09 | AC | 129 ms
26,628 KB |
testcase_10 | AC | 140 ms
43,016 KB |
testcase_11 | AC | 78 ms
19,764 KB |
testcase_12 | AC | 130 ms
26,684 KB |
testcase_13 | AC | 61 ms
16,444 KB |
testcase_14 | AC | 56 ms
16,464 KB |
testcase_15 | AC | 66 ms
17,100 KB |
testcase_16 | AC | 6 ms
7,856 KB |
testcase_17 | AC | 25 ms
11,352 KB |
testcase_18 | AC | 107 ms
24,724 KB |
testcase_19 | AC | 125 ms
26,476 KB |
testcase_20 | AC | 48 ms
15,248 KB |
testcase_21 | AC | 99 ms
24,364 KB |
testcase_22 | AC | 75 ms
17,936 KB |
testcase_23 | AC | 31 ms
11,948 KB |
testcase_24 | AC | 33 ms
11,872 KB |
testcase_25 | AC | 10 ms
8,476 KB |
testcase_26 | AC | 98 ms
24,052 KB |
testcase_27 | AC | 25 ms
11,360 KB |
testcase_28 | AC | 28 ms
11,564 KB |
testcase_29 | AC | 5 ms
8,012 KB |
testcase_30 | AC | 124 ms
26,492 KB |
testcase_31 | AC | 103 ms
24,356 KB |
testcase_32 | AC | 5 ms
7,772 KB |
testcase_33 | AC | 9 ms
8,264 KB |
testcase_34 | AC | 63 ms
19,500 KB |
testcase_35 | AC | 76 ms
19,832 KB |
testcase_36 | AC | 59 ms
19,080 KB |
testcase_37 | AC | 5 ms
8,028 KB |
testcase_38 | AC | 47 ms
13,808 KB |
testcase_39 | AC | 26 ms
10,748 KB |
testcase_40 | AC | 46 ms
13,936 KB |
testcase_41 | AC | 36 ms
13,276 KB |
testcase_42 | AC | 75 ms
19,828 KB |
testcase_43 | AC | 8 ms
8,336 KB |
testcase_44 | AC | 70 ms
19,424 KB |
testcase_45 | AC | 41 ms
13,732 KB |
testcase_46 | AC | 11 ms
8,852 KB |
testcase_47 | AC | 24 ms
10,544 KB |
testcase_48 | AC | 61 ms
19,284 KB |
testcase_49 | AC | 6 ms
7,832 KB |
testcase_50 | AC | 73 ms
19,444 KB |
testcase_51 | AC | 43 ms
13,544 KB |
testcase_52 | AC | 6 ms
7,852 KB |
testcase_53 | AC | 129 ms
26,752 KB |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() //#pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } //--------------------------------------------------------------------------------------------------- /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i @hamayanhamayan0 / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ struct DirectedGraphRangeEdge { int NV; vector<vector<int>> E; void init(int n) { NV = 1; while (NV < n) NV *= 2; E.resize(NV * 2); rep(i, 1, NV) { E[i].push_back(i * 2); E[i].push_back(i * 2 + 1); } } // [x, y) void add(int from, int x, int y) { add(from + NV, x, y, 0, NV, 1); } void add(int from, int x, int y, int l, int r, int k) { if (r <= x || y <= l) return; if (x <= l && r <= y) { E[from].push_back(k); return; } add(from, x, y, l, (l + r) / 2, k * 2); add(from, x, y, (l + r) / 2, r, k * 2 + 1); } }; int N; DirectedGraphRangeEdge dgre; vector<tuple<int, int, int, int>> ABCi; ll ans[101010]; //--------------------------------------------------------------------------------------------------- ll memo[1 << 19]; // -1: not visited -2: pending 0<=: cached infl: BAN ll dfs(int cu) { if (0 <= memo[cu]) return memo[cu]; if (memo[cu] == -2) return memo[cu] = infl; memo[cu] = -2; ll res = 0; fore(to, dgre.E[cu]) chmax(res, dfs(to)); if (res == infl) return infl; if (dgre.NV <= cu) res += get<1>(ABCi[cu - dgre.NV]); return memo[cu] = res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; dgre.init(N); rep(i, 0, N) { int a, b, c; cin >> a >> b >> c; ABCi.push_back(make_tuple(a, b, c, i)); } sort(all(ABCi)); rep(i, 0, N) { int b, c, _; tie(_, b, c, _) = ABCi[i]; int idx = lower_bound(all(ABCi), make_tuple(b - c + 1, -1, -1, -1)) - ABCi.begin(); if (i < idx) { if (0 < i) dgre.add(i, 0, i); if (i + 1 < idx) dgre.add(i, i + 1, idx); } else dgre.add(i, 0, idx); } rep(i, 0, 1 << 19) memo[i] = -1; rep(i, 0, N) ans[get<3>(ABCi[i])] = dfs(i + dgre.NV); rep(i, 0, N) { if (ans[i] == infl) printf("BAN\n"); else printf("%lld\n", ans[i]); } }