結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー antaanta
提出日時 2018-04-06 19:30:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 114 ms / 4,000 ms
コード長 5,241 bytes
コンパイル時間 2,046 ms
コンパイル使用メモリ 186,832 KB
実行使用メモリ 11,604 KB
最終ジャッジ日時 2024-05-03 12:44:52
合計ジャッジ時間 4,221 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 3 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 102 ms
11,604 KB
testcase_30 AC 89 ms
10,068 KB
testcase_31 AC 80 ms
10,192 KB
testcase_32 AC 114 ms
11,604 KB
testcase_33 AC 82 ms
5,376 KB
testcase_34 AC 78 ms
5,376 KB
testcase_35 AC 98 ms
10,196 KB
testcase_36 AC 101 ms
10,196 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

using Val = ll;
const Val infVal = INFL;
struct Sum {
	int num;
	Val minVal;
	Sum() : num(0), minVal(infVal) {}
	Sum(const Val &val, int pos) : num(val == infVal ? 0 : 1), minVal(val) { }
	Sum &operator+=(const Sum &that) {
		num += that.num;
		amin(minVal, that.minVal);
		return *this;
	}
	Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};
struct Add {
	ll sub;
	Add() : sub(0) { }
	Add &operator+=(const Add &that) { sub += that.sub; return *this; }
	void addToVal(Val &val, int pos) const { if (val != infVal) val -= sub; }
	void addToSum(Sum &sum, int left, int right) const {
		if (sum.minVal != infVal)
			sum.minVal -= sub;
	}
};

struct SegmentTree {
	vector<Val> leafs;
	vector<Sum> nodes;
	vector<Add> add;
	vector<int> leftpos, rightpos;
	int n, n2;
	void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
	void init(const vector<Val> &u) {
		n = 1; while (n < (int)u.size()) n *= 2;
		n2 = (n - 1) / 2 + 1;
		leafs = u; leafs.resize(n, Val());
		nodes.resize(n);
		for (int i = n - 1; i >= n2; -- i)
			nodes[i] = Sum(leafs[i * 2 - n], i * 2 - n) + Sum(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
		for (int i = n2 - 1; i > 0; -- i)
			nodes[i] = nodes[i * 2] + nodes[i * 2 + 1];
		add.assign(n, Add());

		leftpos.resize(n); rightpos.resize(n);
		for (int i = n - 1; i >= n2; -- i) {
			leftpos[i] = i * 2 - n;
			rightpos[i] = (i * 2 + 1 - n) + 1;
		}
		for (int i = n2 - 1; i > 0; -- i) {
			leftpos[i] = leftpos[i * 2];
			rightpos[i] = rightpos[i * 2 + 1];
		}
	}
	Val get(int i) {
		int indices[128];
		int k = getIndices(indices, i, i + 1);
		propagateRange(indices, k);
		return leafs[i];
	}
	Sum getRangeCommutative(int i, int j) {
		int indices[128];
		int k = getIndices(indices, i, j);
		propagateRange(indices, k);
		Sum res = Sum();
		for (int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res += sum(l ++);
			if (r & 1) res += sum(-- r);
		}
		return res;
	}
	void set(int i, const Val &x) {
		int indices[128];
		int k = getIndices(indices, i, i + 1);
		propagateRange(indices, k);
		leafs[i] = x;
		mergeRange(indices, k);
	}
	void addToRange(int i, int j, const Add &x) {
		if (i >= j) return;
		int indices[128];
		int k = getIndices(indices, i, j);
		propagateRange(indices, k);
		int l = i + n, r = j + n;
		if (l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
		if (r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
		for (l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) add[l ++] += x;
			if (r & 1) add[-- r] += x;
		}
		mergeRange(indices, k);
	}
private:
	int getIndices(int indices[], int i, int j) const {
		int k = 0, l, r;
		if (i >= j) return 0;
		for (l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
			indices[k ++] = l;
			indices[k ++] = r;
		}
		for (; l; l >>= 1) indices[k ++] = l;
		return k;
	}
	void propagateRange(int indices[], int k) {
		for (int i = k - 1; i >= 0; -- i)
			propagate(indices[i]);
	}
	void mergeRange(int indices[], int k) {
		for (int i = 0; i < k; ++ i)
			merge(indices[i]);
	}
	inline void propagate(int i) {
		if (i >= n) return;
		add[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
		if (i * 2 < n) {
			add[i * 2] += add[i];
			add[i * 2 + 1] += add[i];
		} else {
			add[i].addToVal(leafs[i * 2 - n], i * 2 - n);
			add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
		}
		add[i] = Add();
	}
	inline void merge(int i) {
		if (i >= n) return;
		nodes[i] = sum(i * 2) + sum(i * 2 + 1);
	}
	inline Sum sum(int i) {
		propagate(i);
		return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
	}
public:
	void searchAndSetInf(int i, int j, vector<pair<int, Val>> &out) {
		searchAndSetInfAllRec(1, i, j, out);
	}
private:
	void searchAndSetInfAllRec(int i, int l, int r, vector<pair<int, Val>> &out) {
		propagate(i);
		if (sum(i).minVal > 0) return;
		if (i >= n) {
			if (l <= i - n && i - n < r) {
				out.emplace_back(i - n, leafs[i - n]);
				leafs[i - n] = infVal;
			}
			return;
		}
		amax(l, leftpos[i]);
		amin(r, rightpos[i]);
		if (l >= r) return;
		searchAndSetInfAllRec(i * 2, l, r, out);
		searchAndSetInfAllRec(i * 2 + 1, l, r, out);
		merge(i);
	}
};


int main() {
	int N; int W; long long H;
	while (~scanf("%d%d%lld", &N, &W, &H)) {
		SegmentTree segt;
		segt.init(W, Val(H));
		vector<pair<int, Val>> tmp;
		array<int, 2> score = {0, 0};
		rep(i, N) {
			int a; long long b; int x;
			scanf("%d%lld%d", &a, &b, &x), -- x;
			Add add;
			add.sub = b;
			segt.addToRange(x, x + a, add);
			tmp.clear();
			segt.searchAndSetInf(x, x + a, tmp);
			score[i % 2] += (int)tmp.size();
		}
		puts(score[0] > score[1] ? "A" : score[0] < score[1] ? "B" : "DRAW");
	}
	return 0;
}
0