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; }