結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー vjudge1
提出日時 2025-02-22 20:55:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 137 ms / 4,000 ms
コード長 1,305 bytes
コンパイル時間 2,143 ms
コンパイル使用メモリ 201,628 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2025-02-22 20:55:58
合計ジャッジ時間 4,792 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
typedef long long ll;

struct BIT {
	int N;
	vector<ll> tr;
	BIT(int len) {
		N = len;
		tr.assign(len + 5, 0);
	}
	int lowbit(int x) {
		return x & -x;
	}
	void add(int x, ll v) {
		for (int i = x; i <= N; i += lowbit(i)) 
			tr[i] += v;
	}
	ll qry(int x) {
		ll ret = 0;
		for (int i = x; i; i -= lowbit(i))
			ret += tr[i];
		return ret;
	}
};

typedef pair<int, ll> pii;
int n, w;
ll h;
int a[N], b[N], x[N];

int main(){
  	cin >> n >> w >> h;
  	for (int i = 1; i <= n; i++)
    	cin >> a[i] >> b[i] >> x[i];
  	vector<vector<pii> > add(w + 5);
  	for (int i = 1; i <= n; i++){
    	add[x[i]].push_back(make_pair(i, b[i]));
    	add[x[i] + a[i]].push_back(make_pair(i, -b[i]));
  	}
  	ll A = 0, B = 0;
  	BIT bit(n);
  	for (int i = 1; i <= w; i++) {
    	for (auto P: add[i])
      		bit.add(P.first, P.second);
   		int l = 0, r = n + 1; 
    	while (r - l > 1) {
      		int mid = (r + l) / 2;
      		if (bit.qry(mid) >= h)
        		r = mid;
      		else 
        		l = mid;
    	}
    	if (r != n + 1) {
      		if (r % 2 == 1)
        		A++;
      		else
        		B++;
    	}
  	}
  	if (A > B)
  		puts("A");
  	else if (A < B)
  		puts("B");
  	else
  		puts("DRAW");
//  	cout << A << ' ' << B << endl;
  	return 0;
}
0