ACM-INC Solutions

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

#define REP(i,n) for(int i = 0, _n = (n); i < _n; i++)
#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define FOREACH(it,c) for (__typeof ((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define RESET(c,x) memset (c, x, sizeof (c))
#define SIZE(c) (c).size()

using namespace std;

typedef long long LL;

struct Number {
	LL a, b;
	int c, MOD;
	Number(LL a, LL b, int c, int MOD) : a(a), b(b), c(c), MOD(MOD) {}
	Number(){}
	void normalize(LL &a, LL &b, int c, int MOD) const {
		a += b / c;
		b %= c;
		if (b < 0) a--, b += c;
		a %= MOD;
		if (a < 0) a += MOD;
	}
	Number operator*(const LL &x) const {
		Number ret = Number(a * x % MOD, b * x, c, MOD);
		normalize(ret.a, ret.b, ret.c, ret.MOD);
		return ret;
	}
	Number operator+(const Number &x) const {
		Number ret = Number((a + x.a) % MOD, b + x.b, c, MOD);
		normalize(ret.a, ret.b, ret.c, ret.MOD);
		return ret;
	}
	Number operator-(const Number &x) const {
		Number ret = Number((a - x.a) % MOD, b - x.b, c, MOD);
		normalize(ret.a, ret.b, ret.c, ret.MOD);
		return ret;
	}
};

int nTC, Q, X;
char com[2];

const int BUCSIZE = 143;
const int MAXSIZE = 143;
LL sum[6][MAXSIZE + 5];
deque<int> buc[MAXSIZE + 5];

inline void initDataStructure() {
	RESET(sum, 0);
	REP (i, MAXSIZE + 1) buc[i].clear();
}

inline void add_sum(int where, LL x) {
	LL tmp = 1;
	LL sign = x;
	if (x < 0) x = -x;
	FOR (k, 1, 5) {
		tmp *= x;
		if (sign < 0) sum[k][where] -= tmp;
		else sum[k][where] += tmp;
	}
}

inline int find_idx(int idx, int &ctr) {
	int where = 0;
	while (true) {
		if (idx < ctr + BUCSIZE) break;
		ctr += SIZE(buc[where]);
		where++;
	}
	return where;
}

inline void insert(int idx, int x) {
	int ctr = 0;
	int where = find_idx(idx, ctr);
	buc[where].push_back(0);
	FOREACH(it, buc[where]) {
		if (ctr == idx) {
			add_sum(where, x);
			buc[where].insert(it, x);
			break;
		}
		ctr++;
	}
	buc[where].pop_back();
	while (SIZE(buc[where]) > BUCSIZE) {
		add_sum(where, -buc[where].back());
		add_sum(where + 1, buc[where].back());
		buc[where + 1].push_front(buc[where].back());
		buc[where].pop_back();
		where++;
	}
}

inline void remove(int idx) {
	int ctr = 0;
	int where = find_idx(idx, ctr);
	FOREACH(it, buc[where]) {
		if (ctr == idx) {
			add_sum(where, -(*it));
			buc[where].erase(it);
			break;
		}
		ctr++;
	}
	while (SIZE(buc[where + 1]) > 0) {
		add_sum(where, buc[where + 1].front());
		add_sum(where + 1, -buc[where + 1].front());
		buc[where].push_back(buc[where + 1].front());
		buc[where + 1].pop_front();
		where++;
	}
}

inline LL get_pow(int a, int b) {
	LL ret = 1;
	REP (i, b) ret *= a;
	return ret;
}

inline LL query(int a, int b, int k) {
	LL ret = 0;
	int ctr = 0;
	int where = find_idx(a, ctr);
	while (ctr <= b) {
		if (ctr >= a && ctr % BUCSIZE == 0 && ctr + BUCSIZE - 1 <= b) ret += sum[k][where], ctr += BUCSIZE;
		else {
			FOREACH(it, buc[where]) {
				if (ctr >= a && ctr <= b)
					ret += get_pow(*it, k);
				ctr++;
			}
		}
		where++;
	}
	return ret;
}

inline void printData() {
	int where = 0;
	while (SIZE(buc[where]) > 0) {
		FOREACH(it, buc[where]) printf(" %d", *it);
		where++;
	}
}

inline int f(int xx, int yy, int k, int MOD) {
	Number ret;
	LL S[k + 1];
	FOR (i, 1, k) S[i] = query(xx, yy, i);
	if (k == 0) return 1 % MOD;
	else if (k == 1) return S[1] % MOD;
	else if (k == 2) {
		Number one = Number(0, 1, 2, MOD);
		ret = (one * S[1]) * S[1] - one * S[2];
	} else if (k == 3) {
		Number one = Number(0, 1, 6, MOD);
		ret = ((one * S[1]) * S[1]) * S[1] - ((one * 3) * S[1]) * S[2] + (one * 2) * S[3];
	} else if (k == 4) {
		Number one = Number(0, 1, 24, MOD);
		ret = (((one * S[1]) * S[1]) * S[1]) * S[1] - (((one * 6) * S[1]) * S[1]) * S[2] + ((one * 8) * S[1]) * S[3]
			  + ((one * 3) * S[2]) * S[2] - (one * 6) * S[4];
	} else if (k == 5) {
		Number one = Number(0, 1, 120, MOD);
		ret = ((((one * S[1]) * S[1]) * S[1]) * S[1]) * S[1] - ((((one * 10) * S[1]) * S[1]) * S[1]) * S[2]
			  + (((one * 20) * S[1]) * S[1]) * S[3] + (((one * 15) * S[1]) * S[2]) * S[2] - ((one * 30) * S[1]) * S[4]
			  - ((one * 20) * S[2]) * S[3] + (one * 24) * S[5];
	}
	return ret.a;
}

int main () {
	scanf("%d", &nTC);
	FOR (tc, 1, nTC) {
		initDataStructure();
		X = 0;
		scanf("%d", &Q);
		while (Q--) {
			scanf("%s", com);
			if (com[0] == '+') {
				int a, b, k, c, d, idx;
				scanf("%d%d%d%d%d", &a, &b, &k, &c, &d);
				if (b > X - 1 || a > b) idx = c % (X + 1);
				else idx = (f(a, b, k, X + 1) + c) % (X + 1);
				insert(idx, d);
				X++;
			} else {
				int p;
				scanf("%d", &p);
				remove(p);
				X--;
			}
		}
		printf("Case #%d: %d", tc, X);
		printData();
		puts("");
	}
    return 0;
}

Pages: 1 2 3 4