結果
問題 |
No.511 落ちゲー 〜手作業のぬくもり〜
|
ユーザー |
![]() |
提出日時 | 2025-02-23 16:47:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 4,000 ms |
コード長 | 1,506 bytes |
コンパイル時間 | 1,762 ms |
コンパイル使用メモリ | 166,632 KB |
実行使用メモリ | 11,580 KB |
最終ジャッジ日時 | 2025-02-23 16:47:35 |
合計ジャッジ時間 | 4,751 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define endl '\n' typedef long long ll; const int N = 1e5 + 10; ll n, w, h; struct Node { ll id, val; }; vector<Node> vec[N]; struct Fenwick { vector<ll> bit; inline Fenwick(ll n) : bit(n + 10) {} inline ll lowbit(ll x) { return x & (-x); } inline void add(ll x, ll k) { x++; for (ll i = x; i < bit.size(); i += lowbit(i)) bit[i] += k; } inline ll query(ll x) { x++; ll ans = 0; for (ll i = x; i; i -= lowbit(i)) ans += bit[i]; return ans; } } t(N); int main(int argc, char const *argv[]) { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); ll a = 0, b = 0; cin >> n >> w >> h; for (ll i = 1; i <= n; i++) { ll a, b, x; cin >> a >> b >> x; vec[x].push_back({i, b}); vec[x + a].push_back({i, -b}); } for (ll i = 1; i <= w; i++) { for (auto Info : vec[i]) t.add(Info.id, Info.val); ll l = 1, r = n, ans = -1; while (r >= l) { ll mid = (l + r) >> 1; if (t.query(mid) >= h) ans = mid, r = mid - 1; else l = mid + 1; } if (ans != -1) (ans & 1 ? a++ : b++); } if (a > b) cout << 'A' << endl; else if (a < b) cout << 'B' << endl; else cout << "DRAW" << endl; return 0; }