KUPC2012 F : Acceleration of Network

問題概要

1日1円ずつ貯金する。貯金額がw[i]円を越えたら以後x日間さらに1 or その日からの経過日数 or 経過日数の2乗だけさらに貯金する。目標額w[i]を達成するのが何日になるかとy[i] (y[i]<3.65*10^6)日目の貯金額を求める問題。3.65*10^6以降の日に関してはw[i]を達成する日を答えなくてもよい。

解法

一日ずつシミュレーションする。区間への定数、1次式、2次式への加算はBITを用いて頑張る。係数を整数にするため6倍すると楽。
BIT使わずによりよい計算量でも解けるらしい。

acceptされたコード

これはバグが入っているのに何故か通っていた。セグフォとn^3でオーバーフローが起きる。
セグフォは配列伸ばすことで、オーバーフローは多分ホーナー法で計算すれば回避できるはず。

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long int64;

const int MAX_Y = 3652425;
const int MAX_N = (int)(1e5);
const int MAX_Q = (int)(1e5);
const int MAX_X = (int)(1e4 + 10);
const char* MANY = "Many years later";

typedef int64 bit_t;

struct BinaryIndexedTree{

	static const int MAX_BIT = MAX_Y + 2;//::MAX_Q + ::MAX_X;
	bit_t data[MAX_BIT + 1];
	int size;

	//doubleのときはmemsetはダメ
	void init(){
		size = MAX_BIT;
		memset(data, 0, sizeof(data));
	}

	//[0, n)
	bit_t sum(int n){
		bit_t ret = 0;
		for ( ; n; n -= n&-n) {
			ret += data[n];
		}
		return ret;
	}

	//[from, to)
	bit_t sum(int from, int to){
		return sum(to) - sum(from);
	}

	void add(int n, bit_t x){
		for ( n++; n <= size; n += n&-n) {
			data[n] += x;
		}
	}

};

BinaryIndexedTree bit0, bit1, bit2, bit3;

int64 getSum(int64 n) {
	return bit0.sum(n) + bit1.sum(n) * n + bit2.sum(n) * n * n + bit3.sum(n) * n * n * n;
}

void add0(int left, int right) {
	bit0.add(left, -6*left);
	bit0.add(right, 6*right);
	bit1.add(left, 6);
	bit1.add(right, -6);
}

void add1(int64 left, int64 right) {
	bit0.add(left,  3*(left*left - left));
	bit0.add(right, 3*right*right - 3*(2*left - 1)*right);
	bit1.add(left,  -3*(2*left - 1));
	bit1.add(right, +3*(2*left - 1));
	bit2.add(left,  +3);
	bit2.add(right, -3);
}

void add2(int64 left, int64 right) {
	int64 a1 = (-left), a2 = (-left + 1), a3 = (-2*left + 1);
	int64 t = a1 * a2 * a3;
	bit0.add(left, t);
	bit0.add(right, -t + (right + a1) * (right + a2) * (2*right + a3));
	bit1.add(left,  +(a2*a3 + a1*a3 + 2*a1*a2));
	bit1.add(right, -(a2*a3 + a1*a3 + 2*a1*a2));
	bit2.add(left,  +(2*a1 + 2*a2 + a3));
	bit2.add(right, -(2*a1 + 2*a2 + a3));
	bit3.add(left,  +2);
	bit3.add(right, -2);
}

int N, Q;
int64 ws[MAX_N], xs[MAX_N];
int ys[MAX_Q], ts[MAX_Q];
int64 ansW[MAX_N], ansY[MAX_Q];

void init() {
	scanf("%d%d", &N, &Q);
	for (int i = 0; i < N; ++i) {
		scanf("%lld%d%lld", ws+i, ts+i, xs+i);
		ws[i] *= 6;
	}
	for (int i = 0; i < Q; ++i) {
		scanf("%d", ys+i);
	}
}

void solve() {
	bit0.init();
	bit1.init();
	bit2.init();
	bit3.init();
	memset(ansW, -1, sizeof(ansW));

	int64 idW = 0, idY = 0;
	//for (int i = 0; i < MAX_Q + MAX_X; ++i) {
	for (int i = 0; i <= MAX_Y; ++i) {
		int64 cur = i ? getSum(i) : 0;
		if (idY < Q && ys[idY] == i) {
			ansY[idY] = cur / 6;
			++idY;
		}

		for (; idW < N;) {
			if (ws[idW] <= cur) {
				ansW[idW] = i;
				if (ts[idW] == 0) {
					add0(i, i + xs[idW]);
				}
				else if (ts[idW] == 1) {
					add1(i, i + xs[idW]);
				}
				else if (ts[idW] == 2) {
					add2(i, i + xs[idW]);
				}
				++idW;
			}
			else {
				break;
			}
		}

		add0(i, i+1);
	}


	for (int i = 0; i < N; ++i) {
		if (ansW[i] == -1) {
			puts(MANY);
		}
		else {
			printf("%lld\n", ansW[i]);
		}
	}

	for (int i = 0; i < Q; ++i) {
		printf("%lld\n", ansY[i]);
	}
}

int main() {
	init();
	solve();

	return 0;
}