Submission #74052869

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#define INF INT64_C(1010101010101010101)
#define KI_MAX (1 << 17) /* 131072 */
int64_t ki[KI_MAX * 2 - 1], ki_all[KI_MAX * 2 - 1];
int64_t tiisakunaihou(int64_t a, int64_t b) {
  return a >= b ? a : b;
}
int64_t ki_add_i(int pos, int ss, int se, int qs, int qe, int64_t delta) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    ki_all[pos] += delta;
  } else if (qe <= ss || se <= qs) { /* 完全に外れている */
    /* 何もしない */
  } else {
    int sm = ss + (se - ss) / 2;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define INF INT64_C(1010101010101010101)

#define KI_MAX (1 << 17) /* 131072 */

int64_t ki[KI_MAX * 2 - 1], ki_all[KI_MAX * 2 - 1];

int64_t tiisakunaihou(int64_t a, int64_t b) {
	return a >= b ? a : b;
}

int64_t ki_add_i(int pos, int ss, int se, int qs, int qe, int64_t delta) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		ki_all[pos] += delta;
	} else if (qe <= ss || se <= qs) { /* 完全に外れている */
		/* 何もしない */
	} else {
		int sm = ss + (se - ss) / 2;
		ki[pos] = tiisakunaihou(
			ki_add_i(pos * 2 + 1, ss, sm, qs, qe, delta),
			ki_add_i(pos * 2 + 2, sm, se, qs, qe, delta)
		);
	}
	return ki[pos] + ki_all[pos];
}

void ki_add(int qs, int qe, int64_t delta) {
	ki_add_i(0, 0, KI_MAX, qs, qe, delta);
}

int64_t ki_get_i(int pos, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[pos] + ki_all[pos];
	} else if (qe <= ss || se <= qs) { /* 完全に外れている */
		return -INF;
	} else {
		int sm = ss + (se - ss) / 2;
		return tiisakunaihou(
			ki_get_i(pos * 2 + 1, ss, sm, qs, qe),
			ki_get_i(pos * 2 + 2, sm, se, qs, qe)
		) + ki_all[pos];
	}
}

int64_t ki_get(int qs, int qe) {
	return ki_get_i(0, 0, KI_MAX, qs, qe);
}

struct izumi_s {
	int power, pos;
};

int qs;
struct izumi_s q[KI_MAX];

void qadjust(int pos) {
	for (;;) {
		int maxpos = pos;
		int i;
		for (i = 1; i <= 2; i++) {
			int c = pos * 2 + i;
			if (c < qs && q[c].power > q[maxpos].power) maxpos = c;
		}
		if (maxpos == pos) {
			if (pos == 0) return;
			pos = (pos - 1) / 2;
		} else {
			struct izumi_s temp = q[pos];
			q[pos] = q[maxpos];
			q[maxpos] = temp;
			pos = maxpos;
		}
	}
}

void qadd(int power, int pos) {
	q[qs++] = (struct izumi_s){ power, pos };
	qadjust(qs - 1);
}

struct izumi_s qget(void) {
	struct izumi_s ret;
	if (qs <= 0) exit(72);
	ret = q[0];
	if (--qs > 0) {
		q[0] = q[qs];
		qadjust(0);
	}
	return ret;
}

struct izumi_s qpeek(void) {
	if (qs <= 0) exit(72);
	return q[0];
}

int N, H;
int d[KI_MAX], h[KI_MAX];

int main(void) {
	int i;
	uint64_t ans = 0;
	if (scanf("%d%d", &N, &H) != 2) return 1;
	for (i = 1; i < N; i++) {
		if (scanf("%d%d", &d[i], &h[i]) != 2) return 1;
	}
	ki_add(1, N, H);
	for (i = 1; i < N; i++) {
		int64_t hp = ki_get(i, i + 1) - d[i];
		qadd(h[i], i);
		while (hp <= 0) {
			struct izumi_s top = qpeek();
			int64_t top_hp = ki_get(top.pos, i + 1);
			int64_t cancount = (H - top_hp) / top.power;
			int64_t docount = -hp / top.power + 1;
			if (docount > cancount) docount = cancount;
			hp += top.power * docount;
			ans += docount;
			ki_add(top.pos, N, top.power * docount);
			if (cancount == docount) {
				qget();
				qadd((int)(H - ki_get(top.pos, i + 1)), top.pos);
			}
		}
		ki_add(i + 1, N, -d[i]);
	}
	printf("%" PRIu64 "\n", ans);
	return 0;
}

/*

各階で降りる直前の体力 → BIT
各階の回復の泉の回復力 → プライオリティーキュー

体力が0以下になりそう
→ そこまでで最大の回復力の泉を使う
ただし、回復力が満タンまでの残りを超える場合は、cropして再評価 (各階について高々1回)

↑嘘
その場での満タンだけではなく、それ以降の最大値からの満タンを考慮する
そのため、BITではなくセグメント木を用いる (範囲add, 範囲max)

*/

Submission Info

Judge Result