oj.uz

답안 #128653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128653 2019-07-11T08:05:00 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
35 / 100
 1478 ms 23648 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();
		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) {
		//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) {
		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;
			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(; 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;
			}
			buk[i].pushBack(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(buk[i].n < 2 || 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++) {
			j = buk[i].find(s);
			if(0 <= j) break;
		}
		//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);
			if(0 <= nxt) {
				BUK::cal(buk[nxt].mat[0], s, e, 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) 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) {
	tbl.push(s, e);
	CH.insert({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 12 ms 11768 KB Output is correct
3 Correct 12 ms 11768 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 12 ms 11768 KB Output is correct
6 Correct 11 ms 11640 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 12 ms 11768 KB Output is correct
3 Correct 12 ms 11768 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 12 ms 11768 KB Output is correct
6 Correct 11 ms 11640 KB Output is correct
7 Correct 12 ms 11768 KB Output is correct
8 Correct 12 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 35 ms 23648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 12 ms 11768 KB Output is correct
3 Correct 12 ms 11768 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 12 ms 11768 KB Output is correct
6 Correct 11 ms 11640 KB Output is correct
7 Correct 12 ms 11768 KB Output is correct
8 Correct 12 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 35 ms 23648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 1353 ms 19496 KB Output is correct
3 Correct 1478 ms 18476 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 12 ms 11768 KB Output is correct
3 Correct 12 ms 11768 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 12 ms 11768 KB Output is correct
6 Correct 11 ms 11640 KB Output is correct
7 Correct 12 ms 11768 KB Output is correct
8 Correct 12 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 35 ms 23648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -