oj.uz

Submission #128700

# Submission time Handle Problem Language Result Execution time Memory
128700 2019-07-11T08:32:03 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
50 / 100
 4000 ms 13972 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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 12 ms 11768 KB Output is correct
3 Correct 11 ms 11740 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 11 ms 11768 KB Output is correct
6 Correct 12 ms 11768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 12 ms 11768 KB Output is correct
3 Correct 11 ms 11740 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 11 ms 11768 KB Output is correct
6 Correct 12 ms 11768 KB Output is correct
7 Correct 11 ms 11768 KB Output is correct
8 Correct 12 ms 11772 KB Output is correct
9 Correct 12 ms 11768 KB Output is correct
10 Correct 12 ms 11768 KB Output is correct
11 Correct 12 ms 11768 KB Output is correct
12 Correct 12 ms 11896 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11768 KB Output is correct
2 Correct 12 ms 11784 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 12 ms 11768 KB Output is correct
3 Correct 11 ms 11740 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 11 ms 11768 KB Output is correct
6 Correct 12 ms 11768 KB Output is correct
7 Correct 11 ms 11768 KB Output is correct
8 Correct 12 ms 11772 KB Output is correct
9 Correct 12 ms 11768 KB Output is correct
10 Correct 12 ms 11768 KB Output is correct
11 Correct 12 ms 11768 KB Output is correct
12 Correct 12 ms 11896 KB Output is correct
13 Correct 11 ms 11768 KB Output is correct
14 Correct 12 ms 11784 KB Output is correct
15 Correct 11 ms 11768 KB Output is correct
16 Correct 12 ms 11768 KB Output is correct
17 Correct 12 ms 11768 KB Output is correct
18 Correct 12 ms 11768 KB Output is correct
19 Correct 12 ms 11768 KB Output is correct
20 Correct 12 ms 11768 KB Output is correct
21 Correct 12 ms 11768 KB Output is correct
22 Correct 12 ms 11808 KB Output is correct
23 Correct 12 ms 11768 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Execution timed out 4100 ms 13972 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 12 ms 11768 KB Output is correct
3 Correct 11 ms 11740 KB Output is correct
4 Correct 11 ms 11768 KB Output is correct
5 Correct 11 ms 11768 KB Output is correct
6 Correct 12 ms 11768 KB Output is correct
7 Correct 11 ms 11768 KB Output is correct
8 Correct 12 ms 11772 KB Output is correct
9 Correct 12 ms 11768 KB Output is correct
10 Correct 12 ms 11768 KB Output is correct
11 Correct 12 ms 11768 KB Output is correct
12 Correct 12 ms 11896 KB Output is correct
13 Correct 11 ms 11768 KB Output is correct
14 Correct 12 ms 11784 KB Output is correct
15 Correct 11 ms 11768 KB Output is correct
16 Correct 12 ms 11768 KB Output is correct
17 Correct 12 ms 11768 KB Output is correct
18 Correct 12 ms 11768 KB Output is correct
19 Correct 12 ms 11768 KB Output is correct
20 Correct 12 ms 11768 KB Output is correct
21 Correct 12 ms 11768 KB Output is correct
22 Correct 12 ms 11808 KB Output is correct
23 Correct 12 ms 11768 KB Output is correct
24 Correct 12 ms 11768 KB Output is correct
25 Execution timed out 4100 ms 13972 KB Time limit exceeded
26 Halted 0 ms 0 KB -