Block Stacking Game

[qiaobaaa]

include

include

using namespace std;

define MAX(a,b) (a>b?a:b)

define MIN(a,b) (a<b?a:b)

define MAXC 1000000

//利用线段树进行记录，经验表明开4倍空间不会越界，也没有超过256MB限制 int mSegTree[4 MAXC], mMin[4 MAXC], mMax[4 * MAXC];

struct Result { int top; int count; };

//整体思路利用线段树的特性去存储不同的值，并进行更新，整体查询复杂度在O(logN)

long long int mTotal; int C;

void update(int idx, int sSt, int sEn, int qSt, int qEn, int mChange) { //lazy Propagation //进行修改时，事实上并没有真的修改，是给区间打上一段标记,一旦查询时发现这个节点有标记，就把标记下推到它的两个子节点 if (mSegTree[idx] != 0) { register int val = mSegTree[idx]; mMin[idx] += val; mMax[idx] += val; mSegTree[idx] = 0; if (sSt != sEn) { mSegTree[(idx << 1) + 1] += val; mSegTree[(idx << 1) + 2] += val; } } //区间无交集，进行剪枝操作 if (qEn < sSt || sEn<qSt || sSt>sEn) return; //从顶开始 if (sSt >= qSt && sEn <= qEn) { mMin[idx] += mChange; mMax[idx] += mChange; if (sSt != sEn) { mSegTree[(idx << 1) + 1] += mChange; mSegTree[(idx << 1) + 2] += mChange; } return; } register int mid = (sSt + sEn) >> 1; //mid则为中间点，左儿子的结点区间为[sSt,mid],右儿子的结点区间为[mid,sEn] update((idx << 1) + 1, sSt, mid, qSt, qEn, mChange); ////递归构造左儿子结点 update((idx << 1) + 2, mid + 1, sEn, qSt, qEn, mChange); //递归构造右儿子结点 //最大最小的更新 mMin[idx] = MIN(mMin[(idx << 1) + 1], mMin[(idx << 1) + 2]); mMax[idx] = MAX(mMax[(idx << 1) + 1], mMax[(idx << 1) + 2]); }

void init(int C) { ::C = C; mTotal = 0; memset(mSegTree, 0, sizeof(mSegTree)); memset(mMin, 0, sizeof(mMin)); memset(mMax, 0, sizeof(mMax)); }

Result dropBlocks(int mCol, int mHeight, int mLength) { //Do RangeUpdate->Add total blocks->Subtract blocks=no of rows filled update(0, 0, C - 1, mCol, mCol + mLength - 1, mHeight); mTotal += (mHeight mLength); Result ret = { mMax[0] - mMin[0],(mTotal - (C mMin[0])) % MAXC }; return ret; }

[qiaobaaa]

iostream