#118937 (C++11) No.426 往復漸化式

提出ソース

結果

問題	No.426 往復漸化式
ユーザー	colun
提出日時	2016-09-23 00:57:09
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	1,466 ms / 5,000 ms
コード長	7,247 bytes
コンパイル時間	1,194 ms
コンパイル使用メモリ	90,504 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-04-28 20:21:46
合計ジャッジ時間	4,846 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	6 ms 6,940 KB
testcase_04	AC	5 ms 6,944 KB
testcase_05	AC	92 ms 6,944 KB
testcase_06	AC	95 ms 6,940 KB
testcase_07	AC	97 ms 6,940 KB
testcase_08	AC	101 ms 6,940 KB
testcase_09	AC	437 ms 6,940 KB
testcase_10	AC	407 ms 6,940 KB
testcase_11	AC	8 ms 6,940 KB
testcase_12	AC	13 ms 6,940 KB
testcase_13	AC	1,466 ms 6,944 KB
testcase_14	AC	15 ms 6,940 KB
testcase_15	AC	12 ms 6,940 KB
testcase_16	AC	20 ms 6,940 KB
testcase_17	AC	20 ms 6,944 KB
testcase_18	AC	19 ms 6,944 KB
testcase_19	AC	4 ms 6,944 KB
testcase_20	AC	7 ms 6,944 KB
testcase_21	AC	11 ms 6,944 KB
testcase_22	AC	7 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define NDEBUG

#undef __STRICT_ANSI__

#include <string>
#include <cstdlib>
#include <cstdio>
#include <tuple>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <functional>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <cassert>

using namespace std;

#undef assert
#define assert(e)

#include <cstdarg>

typedef long long int64;

#include <sys/time.h>

class XsRandom {
	unsigned long long a;
	unsigned long long b;
public:
	inline XsRandom() : a(0x8a5cd789635d2dffULL), b(0x121fd2155c472f96ULL) {
	}
	inline XsRandom(const XsRandom & o) : a(o.a), b(o.b) {
	}
	inline unsigned long long next64() {
		unsigned long long c = a ^ (a<<23);
		a = b;
		b = c ^ a ^ (c>>18) ^ (a>>5);
		return b + a;
	}
	inline XsRandom(unsigned int seed) : a(0x8a5cd789635d2dffULL), b(0x121fd2155c472f96ULL) {
		seed = seed * 1234567891 + 521288629;
		unsigned long long a2 = a;
		unsigned long long b2 = b;
		while(seed) {
			next64();
			if(seed & 1) {
				a2 ^= a;
				b2 ^= b;
			}
			seed >>= 1;
		}
		a = a2;
		b = b2;
	}
	inline unsigned int next() {
		return (unsigned int)next64();
	}
	inline int nextInt(int r) {
		assert(1<=r);
		return ((unsigned long long)next() * r)>>32;
	}
};

typedef XsRandom MyRandom;

MyRandom g_myRand;

double g_startTime;
double g_suspendTime = 0;
const double g_timeupSecBase = 9.8;
double g_timeupSec = g_timeupSecBase;

#include <numeric>

const char * nextCLineOrWord(int mode) {
	static char buf[65536];
	static int bufLen = sizeof(buf);
	static int bufPos = sizeof(buf);
	static bool canReadFlag = true;
	static bool crFlag = false;
	static bool enterFlag = false;
	if(mode==0) {
		while(true) {
			char c = buf[bufPos];
			if(c==32 || c==10 || c==13) {
				++bufPos;
			}
			else {
				break;
			}
		}
	}
	if(canReadFlag && (enterFlag ? bufLen<=bufPos : (int)sizeof(buf)<=bufPos+bufPos)) {
		if(0<bufLen-bufPos) {
			memmove(buf, buf+bufPos, bufLen-bufPos);
			bufLen -= bufPos;
		}
		else {
			bufLen = 0;
		}
		char * result = fgets(buf+bufLen, sizeof(buf)-bufLen, stdin);
		canReadFlag = (result!=NULL);
		if(result!=NULL) {
			int n = strlen(result);
			enterFlag = (n!=(int)sizeof(buf)-1-bufLen || (1<=bufLen+n && buf[bufLen+n-1]=='\n'));
			bufLen += n;
		}
		bufPos = 0;
	}
	if(mode==0) {
		int pos = bufPos;
		while(true) {
			char c = buf[pos];
			if(c==32) {
				buf[pos++] = '\0';
				break;
			}
			else if(c==10) {
				if(crFlag) {
					crFlag = false;
					if(bufPos==pos) {
						pos = ++bufPos;
						continue;
					}
				}
				buf[pos++] = '\0';
				break;
			}
			else if(c==13) {
				crFlag = true;
				buf[pos++] = '\0';
				break;
			}
			else if(c==0) {
				break;
			}
			++pos;
		}
		const char * ret = buf + bufPos;
		bufPos = pos;
		return ret;
	}
	else if(mode==1) {
		int pos = bufPos;
		while(true) {
			char c = buf[pos];
			if(c==10) {
				if(crFlag) {
					crFlag = false;
					if(bufPos==pos) {
						pos = ++bufPos;
						continue;
					}
				}
				buf[pos++] = '\0';
				break;
			}
			else if(c==13) {
				crFlag = true;
				buf[pos++] = '\0';
				break;
			}
			else if(c==0) {
				break;
			}
			++pos;
		}
		const char * ret = buf + bufPos;
		bufPos = pos;
		return ret;
	}
	else if(mode==2) {
		return bufLen<=bufPos ? NULL : buf+bufPos;
	}
	assert(false);
	return NULL;
}

const char * nextCWord() {
	return nextCLineOrWord(0);
}

string nextWord() {
	return nextCWord();
}

int nextInt() {
	return atoi(nextCWord());
}

int64 nextInt64() {
	return atoll(nextCWord());
}

vector<int> nextIntVec(int n) {
	vector<int> ret;
	for(int i=0; i<n; ++i) {
		ret.push_back(nextInt());
	}
	return ret;
}

vector<int64> nextInt64Vec(int n) {
	vector<int64> ret;
	for(int i=0; i<n; ++i) {
		ret.push_back(nextInt64());
	}
	return ret;
}

void echoln() {
	fputc('\n', stdout);
}
void echoln(const char * fmt, ...) {
	va_list arg;
	va_start(arg, fmt);
	vprintf(fmt, arg);
	va_end(arg);
	fputc('\n', stdout);
}

int main() {
	int n = nextInt();
	map<int, vector<int> > A;
	map<int, vector<int>, greater<int> > B;
	vector<int64> a0 = nextInt64Vec(3);
	vector<int64> bn = nextInt64Vec(2);
	int q = nextInt();
	for(int j=0; j<q; ++j) {
		string w = nextWord();
		if(w=="a") {
			int i = nextInt();
			A[i] = nextIntVec(9);
		}
		else if(w=="b") {
			int i = nextInt();
			B[i] = nextIntVec(4);
		}
		else if(w=="ga") {
			int i = nextInt();
			vector<int64> a = a0;
			for(auto & o : A) {
				if(i<=o.first) {
					break;
				}
				auto & x = o.second;
				int64 a1 = x[0] * a[0] + x[1] * a[1] + x[2] * a[2];
				int64 a2 = x[3] * a[0] + x[4] * a[1] + x[5] * a[2];
				int64 a3 = x[6] * a[0] + x[7] * a[1] + x[8] * a[2];
				a[0] = a1 % 1000000007;
				a[1] = a2 % 1000000007;
				a[2] = a3 % 1000000007;
			}
			echoln("%d %d %d", (int)a[0], (int)a[1], (int)a[2]);
			fflush(stdout);
		}
		else if(w=="gb") {
			int i = nextInt();
			vector<int64> a = a0;
			vector<pair<int, vector<int64> > > AA;
			AA.emplace_back(-1, a);
			AA.emplace_back(-1, a);
			for(auto & o : A) {
				AA.emplace_back(o.first, a);
				auto & x = o.second;
				int64 a1 = x[0] * a[0] + x[1] * a[1] + x[2] * a[2];
				int64 a2 = x[3] * a[0] + x[4] * a[1] + x[5] * a[2];
				int64 a3 = x[6] * a[0] + x[7] * a[1] + x[8] * a[2];
				a[0] = a1 % 1000000007;
				a[1] = a2 % 1000000007;
				a[2] = a3 % 1000000007;
			}
			vector<int64> b = bn;
			int64 t = n;
			for(auto & o : B) {
				if(!(i<o.first)) {
					break;
				}
				int t3 = o.first;
				while(t3<=AA.back().first) {
					int64 t2 = AA.back().first + 1;
					int64 nn = (t-t2+1);
					int64 iSum6 = ((t2 + t) * (t-t2+1) * 3) % 1000000007;
					b[0] = (b[0] + iSum6 * a[0] + (iSum6+nn) * a[1] + (iSum6+nn*2) * a[2]) % 1000000007;
					b[1] = (b[1] + (iSum6+nn*3) * a[0] + (iSum6+nn*4) * a[1] + (iSum6+nn*5) * a[2]) % 1000000007;
					a = AA.back().second;
					AA.pop_back();
					t = t2-1;
				}
				if(t3!=t){
					int64 t2 = t3 + 1;
					int64 nn = (t-t2+1);
					int64 iSum6 = ((t2 + t) * (t-t2+1) * 3) % 1000000007;
					b[0] = (b[0] + iSum6 * a[0] + (iSum6+nn) * a[1] + (iSum6+nn*2) * a[2]) % 1000000007;
					b[1] = (b[1] + (iSum6+nn*3) * a[0] + (iSum6+nn*4) * a[1] + (iSum6+nn*5) * a[2]) % 1000000007;
					t = t3;
				}
				int64 t6 = 6*t;
				auto & x = o.second;
				int64 b1 = (x[0] * b[0] + x[1] * b[1] + t6*a[0] + (t6+1)*a[1] + (t6+2)*a[2]) % 1000000007;
				int64 b2 = (x[2] * b[0] + x[3] * b[1] + (t6+3)*a[0] + (t6+4)*a[1] + (t6+5)*a[2]) % 1000000007;
				b[0] = b1;
				b[1] = b2;
				--t;
			}
			while(i<=AA.back().first) {
				int64 t2 = AA.back().first + 1;
				int64 nn = (t-t2+1);
				int64 iSum6 = ((t2 + t) * (t-t2+1) * 3) % 1000000007;
				b[0] = (b[0] + iSum6 * a[0] + (iSum6+nn) * a[1] + (iSum6+nn*2) * a[2]) % 1000000007;
				b[1] = (b[1] + (iSum6+nn*3) * a[0] + (iSum6+nn*4) * a[1] + (iSum6+nn*5) * a[2]) % 1000000007;
				a = AA.back().second;
				AA.pop_back();
				t = t2-1;
			}
			if(i!=t){
				int64 t2 = i + 1;
				int64 nn = (t-t2+1);
				int64 iSum6 = ((t2 + t) * (t-t2+1) * 3) % 1000000007;
				b[0] = (b[0] + iSum6 * a[0] + (iSum6+nn) * a[1] + (iSum6+nn*2) * a[2]) % 1000000007;
				b[1] = (b[1] + (iSum6+nn*3) * a[0] + (iSum6+nn*4) * a[1] + (iSum6+nn*5) * a[2]) % 1000000007;
				t = i;
			}
			echoln("%d %d", (int)b[0], (int)b[1]);
			fflush(stdout);
		}
	}

	return 0;
}

yukicoder

結果

テストケース

ソースコード