oj.uz

답안 #128664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128664 2019-07-11T08:13:43 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
20 / 100
 4000 ms 13852 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) {
		if(!n) fuk();
		//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();
		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;
			}
			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 < SQRN+5; i++) {
			j = buk[i].find(s);
			if(0 <= j) break;
		}
		if(j < 0) fuk();
		//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();
			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 11 ms 11768 KB Output is correct
3 Correct 11 ms 11772 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 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 11772 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 11768 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 11772 KB Output is correct
10 Correct 12 ms 11772 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 11772 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 11 ms 11768 KB Output is correct
3 Correct 11 ms 11772 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 11768 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 11772 KB Output is correct
10 Correct 12 ms 11772 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 12 ms 11768 KB Output is correct
2 Execution timed out 4086 ms 13852 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 11772 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 11768 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 11772 KB Output is correct
10 Correct 12 ms 11772 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 -