oj.uz

답안 #128688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128688 2019-07-11T08:28:04 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
20 / 100
 4000 ms 13668 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline void fuk() { puts("ERR!"); exit(-1); }

const int MOD = 1000000007;

struct MAT {
	MAT(int a = 1, int b = 0, int c = 0, int d = 1)
		: a(a), b(b), c(c), d(d) {}
	// a b
	// c d
	int a, b, c, d;

	void init() { a = d = 1; b = c = 0; }
	MAT operator * (const MAT &t) const {
		return MAT((ll(a)*t.a + ll(b)*t.c)%MOD, (ll(a)*t.b + ll(b)*t.d)%MOD
				 , (ll(c)*t.a + ll(d)*t.c)%MOD, (ll(c)*t.b + ll(d)*t.d)%MOD);
	}
	//void prt() { printf("[%d/%d/%d/%d] ", a, b, c, d); }
};

const int MAXN = 100005;
const int SQRN = 450;

struct BUK {
	MAT mat[SQRN*2+5], matProd;
	int S[SQRN*2+5], E[SQRN*2+5];
	int n;

	void init() { n = 0; matProd.init(); }
	static void cal(MAT &mat, int ps, int pe, int s, int e) {
		if(ps < 0) { mat.init(); return; }
		int l = s-pe-1, c = (e-s)>>1;
		//printf("CAL ps=%d, pe=%d, s=%d, e=%d :: l=%d, c=%d : ", ps, pe, s, e, l, c);
		mat.a = (l+1)>>1; mat.b = l>>1;
		mat.c = (ll(c)*((l+1)>>1) + 1) % MOD;
		mat.d = (ll(c)*(l>>1) + 1) % MOD;
		//mat.prt(); puts("");
	}
	void calAll() {
		matProd.init();
		for(int i = 0; i < n; i++)
			matProd = mat[i] * matProd;
	}
	int find(int X) {
		if(!n || X < S[0] || E[n-1] < X) return -1;
		int i = 0; for(; i < n && S[i] < X; i++);
		return i;
	}
	void push(int s, int e) {
		int i = 0; for(; i < n && S[i] < s; i++);
		if(!i || i == n) fuk(); // TODO
		for(int j = n; i < j; j--) {
			swap(mat[j-1], mat[j]);
			S[j] = S[j-1];
			E[j] = E[j-1];
		}
		S[i] = s; E[i] = e; n++;
		cal(mat[i], S[i-1], E[i-1], s, e);
		cal(mat[i+1], s, e, S[i+1], E[i+1]);
	}
	void pushFront(int ps, int pe, int s, int e) {
		if(!n) fuk(); // TODO
		//printf("PUSHFRONT %d %d / %d %d\n", ps, pe, s, e);
		for(int i = n; i; i--) {
			swap(mat[i-1], mat[i]);
			S[i] = S[i-1];
			E[i] = E[i-1];
		}
		S[0] = s; E[0] = e; n++;
		cal(mat[0], ps, pe, s, e);
		cal(mat[1], s, e, S[1], E[1]);
	}
	void pushBack(int s, int e) {
		if(!n) fuk(); // TODO
		S[n] = s; E[n] = e;
		cal(mat[n], S[n-1], E[n-1], s, e);
		n++;
	}
	void pushNew(int ps, int pe, int s, int e) {
		S[0] = s; E[0] = e; n = 1;
		cal(mat[0], ps, pe, s, e);
	}
	void pop(int ps, int pe, int i) {
		//printf("POP %d %d %d\n", ps, pe, i);
		cal(mat[i+1], ps, pe, S[i+1], E[i+1]);
		for(int j = i+1; j < n; j++) {
			swap(mat[j-1], mat[j]);
			S[j-1] = S[j];
			E[j-1] = E[j];
		}
		n--;
	}
};

struct TBL {
	BUK buk[SQRN+5];

	MAT mat[MAXN*2];
	int S[MAXN*2], E[MAXN*2];
	int n, qn;

	void release() {
		n = qn = 0;
		for(int i = 0; i < SQRN+5; i++) {
			for(int j = 0; j < buk[i].n; j++) {
				mat[n] = buk[i].mat[j];
				S[n] = buk[i].S[j];
				E[n] = buk[i].E[j];
				n++;
			}
			buk[i].init();
		}
		for(int s = 0, e, i = 0;;) {
			e = s+SQRN-1;
			if(n <= e) e = n-1;
			if(s > e) break;
			buk[i].n = e-s+1;
			for(int j = s, c = 0; j <= e; j++) {
				buk[i].mat[c] = mat[j];
				buk[i].S[c] = S[j];
				buk[i].E[c] = E[j];
				c++;
			}
			buk[i].calAll();
			s = e+1; i++;
		}
	}

	int findNxt(int i) {
		for(i++; i < SQRN+5 && !buk[i].n; i++);
		return SQRN+5 <= i ? -1 : i;
	}
	int findPrev(int i) {
		for(i--; 0 <= i && !buk[i].n; i--);
		return i;
	}
	void findPrev(int i, int j, int &ps, int &pe) {
		//printf("findPrev %d %d\n", i, j);
		if(j) {
			ps = buk[i].S[j-1];
			pe = buk[i].E[j-1];
			return;
		}
		i = findPrev(i);
		if(0 <= i) {
			ps = buk[i].S[buk[i].n-1];
			pe = buk[i].E[buk[i].n-1];
			return;
		}
		ps = pe = -1;
	}

	void _push(int s, int e) {
		int i = 0;
		for(; i < SQRN+5 && buk[i].n && buk[i].E[buk[i].n-1] < s; i++);
		if(SQRN+3 < i) {
			i = SQRN+3;
			if(!buk[i].n) {
				int ps, pe; findPrev(i, 0, ps, pe);
				buk[i].pushNew(ps, pe, s, e);
				buk[i].calAll();
				return;
			}
			if(e < buk[i].S[0]) {
				int ps, pe; findPrev(i, 0, ps, pe);
				buk[i].pushFront(ps, pe, s, e);
				buk[i].calAll();
				return;
			}
			if(buk[i].E[buk[i].n-1] < s) {
				buk[i].pushBack(s, e);
				buk[i].calAll();
				return;
			}
			buk[i].push(s, e);
			buk[i].calAll();
			return;
		}
		//printf("PUSH %d %d / %d\n", s, e, i);
		if(!buk[i].n) {
			int ps, pe; findPrev(i, 0, ps, pe);
			buk[i].pushNew(ps, pe, s, e);
			buk[i].calAll();
			int nxt = findNxt(i);
			if(0 <= nxt) {
				BUK::cal(buk[nxt].mat[0], s, e, buk[nxt].S[0], buk[nxt].E[0]);
				buk[nxt].calAll();
			}
			return;
		}
		if(e < buk[i].S[0]) {
			int ps, pe; findPrev(i, 0, ps, pe);
			buk[i].pushFront(ps, pe, s, e);
			buk[i].calAll();
			return;
		}
		buk[i].push(s, e);
		buk[i].calAll();
	}

	void _pop(int s, int e) {
		int i = 0, j = -1;
		for(; i < SQRN+5; i++) {
			j = buk[i].find(s);
			if(0 <= j) break;
		}
		if(j < 0) fuk(); // TODO
		//printf("POP %d %d / %d %d | %d\n", s, e, i, j, buk[i].n);
		if(buk[i].n-1 == j) {
			int nxt = findNxt(i);
			//printf("BACK %d\n", nxt);
			int ps, pe; findPrev(i, j, ps, pe);
			if(0 <= nxt) {
				BUK::cal(buk[nxt].mat[0], ps, pe, buk[nxt].S[0], buk[nxt].E[0]);
				buk[nxt].calAll();
			}
			buk[i].n--;
			buk[i].calAll();
			return;
		}
		int ps, pe; findPrev(i, j, ps, pe);
		//printf("result ps=%d, pe=%d\n", ps, pe);
		buk[i].pop(ps, pe, j);
		buk[i].calAll();
	}

	void push(int s, int e) {
		qn++;
		_push(s, e);
		if(SQRN == qn) release();
	}
	void pop(int s, int e) {
		qn++;
		_pop(s, e);
		if(SQRN == qn) release();
	}
	/*
	void prt() {
		for(int i = 0; i <= 3; i++) {
			printf("BUK %d : %d | ", i, buk[i].n);
			for(int j = 0; j < buk[i].n; j++)
				printf("(%d,%d) ", buk[i].S[j], buk[i].E[j]);
			puts("");
			for(int j = 0; j < buk[i].n; j++)
				buk[i].mat[j].prt();
			puts("");
		}
		puts("");
	}
	*/
	MAT get() {
		MAT ret;
		for(int i = 0; i < SQRN+5; i++) if(buk[i].n) {
			buk[i].calAll(); // TODO erase
			ret = buk[i].matProd * ret;
		}
		return ret;
	}
} tbl;




set<pii> CH;

set<pii>::iterator get(int X) { return prev(CH.upper_bound({X, INF})); }
bool has(int X) {
	auto it = CH.upper_bound({X, INF});
	if(CH.begin() == it) return false;
	int s, e; tie(s, e) = *prev(it);
	return s <= X && X <= e && (s&1) == (X&1);
}

void insert(int s, int e) {
	bool flag = CH.insert({s, e}).second;
	if(flag) tbl.push(s, e);
}
void erase(set<pii>::iterator it) {
	tbl.pop(it->first, it->second);
	CH.erase(it);
}

void push(int X) {
	if(X < 1) return;
	if(1 == X) X = 2;
	if(!has(X)) {
		if(has(X-1) && !has(X+1)) {
			auto it = get(X-1);
			int s, e; tie(s, e) = *it;
			erase(it);
			e -= 2;
			if(s <= e) insert(s, e);
			push(X+1);
			return;
		}
		if(!has(X-1) && has(X+1)) {
			auto it = get(X+1);
			int s, e; tie(s, e) = *it;
			erase(it);
			push(e+1);
			return;
		}
		if(has(X-1) && has(X+1)) {
			auto it = get(X);
			int s, e; tie(s, e) = *it;
			erase(it);
			insert(s, X-1);
			push(e+1);
			return;
		}
		int s = X, e = X;
		if(has(X-2)) {
			auto it = get(X-2);
			int p, q; tie(p, q) = *it;
			erase(it);
			s = p;
		}
		if(has(X+2)) {
			auto it = get(X+2);
			int p, q; tie(p, q) = *it;
			erase(it);
			e = q;
		}
		insert(s, e);
		return;
	}

	auto it = get(X);
	int s, e; tie(s, e) = *it;
	erase(it);
	if(s+1 < X) insert(s+1, X-1);
	push(e+1);
	push(s-2);
}


int N;

ll getAns() {
	if(CH.empty()) return 0;
	MAT mat = tbl.get();
	int s, e; tie(s, e) = *CH.begin();
	ll a = 0, b;
	if(1 < s-2) a = (ll(s-4)/2 + 1) % MOD;
	b = (1 + ll(s-2)/2 * ((e-s)/2)) % MOD;

	//printf("getAns %d %d / %lld %lld\n", s, e, a, b);

	ll ret = a*mat.a % MOD;
	ret += b*mat.b % MOD;
	ret += a*mat.c % MOD;
	ret += b*mat.d % MOD;
	return ret % MOD;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 0; i < N; i++) {
		int x;
		cin >> x;
		push(x+1);
		printf("%lld\n", getAns());
		//tbl.prt();
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 11 ms 11768 KB Output is correct
3 Correct 11 ms 11768 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 11 ms 11768 KB Output is correct
6 Correct 13 ms 11768 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 11 ms 11768 KB Output is correct
3 Correct 11 ms 11768 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 11 ms 11768 KB Output is correct
6 Correct 13 ms 11768 KB Output is correct
7 Correct 14 ms 11768 KB Output is correct
8 Correct 11 ms 11768 KB Output is correct
9 Correct 12 ms 11768 KB Output is correct
10 Correct 12 ms 11768 KB Output is correct
11 Runtime error 12 ms 11768 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 11 ms 11768 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 11 ms 11768 KB Output is correct
3 Correct 11 ms 11768 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 11 ms 11768 KB Output is correct
6 Correct 13 ms 11768 KB Output is correct
7 Correct 14 ms 11768 KB Output is correct
8 Correct 11 ms 11768 KB Output is correct
9 Correct 12 ms 11768 KB Output is correct
10 Correct 12 ms 11768 KB Output is correct
11 Runtime error 12 ms 11768 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11768 KB Output is correct
2 Execution timed out 4026 ms 13668 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 11 ms 11768 KB Output is correct
3 Correct 11 ms 11768 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 11 ms 11768 KB Output is correct
6 Correct 13 ms 11768 KB Output is correct
7 Correct 14 ms 11768 KB Output is correct
8 Correct 11 ms 11768 KB Output is correct
9 Correct 12 ms 11768 KB Output is correct
10 Correct 12 ms 11768 KB Output is correct
11 Runtime error 12 ms 11768 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -