oj.uz

Submission #128703

# Submission time Handle Problem Language Result Execution time Memory
128703 2019-07-11T08:33:03 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
100 / 100
 3761 ms 20052 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
		if(buk[i].n-1 == j) {
			int nxt = findNxt(i);
			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);
		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();
	}
	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 12 ms 11768 KB Output is correct
4 Correct 12 ms 11768 KB Output is correct
5 Correct 12 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 12 ms 11768 KB Output is correct
4 Correct 12 ms 11768 KB Output is correct
5 Correct 12 ms 11768 KB Output is correct
6 Correct 12 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 14 ms 11768 KB Output is correct
10 Correct 14 ms 11768 KB Output is correct
11 Correct 14 ms 11768 KB Output is correct
12 Correct 12 ms 11768 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11768 KB Output is correct
2 Correct 14 ms 11768 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 12 ms 11768 KB Output is correct
4 Correct 12 ms 11768 KB Output is correct
5 Correct 12 ms 11768 KB Output is correct
6 Correct 12 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 14 ms 11768 KB Output is correct
10 Correct 14 ms 11768 KB Output is correct
11 Correct 14 ms 11768 KB Output is correct
12 Correct 12 ms 11768 KB Output is correct
13 Correct 13 ms 11768 KB Output is correct
14 Correct 14 ms 11768 KB Output is correct
15 Correct 12 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 11 ms 11768 KB Output is correct
19 Correct 12 ms 11768 KB Output is correct
20 Correct 12 ms 11772 KB Output is correct
21 Correct 12 ms 11772 KB Output is correct
22 Correct 12 ms 11772 KB Output is correct
23 Correct 12 ms 11768 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Correct 1369 ms 19608 KB Output is correct
3 Correct 1533 ms 18148 KB Output is correct

Subtask #6
35.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 12 ms 11768 KB Output is correct
4 Correct 12 ms 11768 KB Output is correct
5 Correct 12 ms 11768 KB Output is correct
6 Correct 12 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 14 ms 11768 KB Output is correct
10 Correct 14 ms 11768 KB Output is correct
11 Correct 14 ms 11768 KB Output is correct
12 Correct 12 ms 11768 KB Output is correct
13 Correct 13 ms 11768 KB Output is correct
14 Correct 14 ms 11768 KB Output is correct
15 Correct 12 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 11 ms 11768 KB Output is correct
19 Correct 12 ms 11768 KB Output is correct
20 Correct 12 ms 11772 KB Output is correct
21 Correct 12 ms 11772 KB Output is correct
22 Correct 12 ms 11772 KB Output is correct
23 Correct 12 ms 11768 KB Output is correct
24 Correct 12 ms 11768 KB Output is correct
25 Correct 1369 ms 19608 KB Output is correct
26 Correct 1533 ms 18148 KB Output is correct
27 Correct 320 ms 14320 KB Output is correct
28 Correct 565 ms 15944 KB Output is correct
29 Correct 88 ms 12156 KB Output is correct
30 Correct 615 ms 15556 KB Output is correct
31 Correct 1199 ms 13000 KB Output is correct
32 Correct 1201 ms 14848 KB Output is correct
33 Correct 1792 ms 13232 KB Output is correct
34 Correct 159 ms 12672 KB Output is correct
35 Correct 1747 ms 13488 KB Output is correct
36 Correct 1861 ms 13096 KB Output is correct
37 Correct 780 ms 12964 KB Output is correct
38 Correct 1358 ms 20052 KB Output is correct
39 Correct 139 ms 12276 KB Output is correct
40 Correct 165 ms 12372 KB Output is correct
41 Correct 2097 ms 13256 KB Output is correct
42 Correct 1361 ms 19680 KB Output is correct
43 Correct 210 ms 13832 KB Output is correct
44 Correct 194 ms 13680 KB Output is correct
45 Correct 3698 ms 14308 KB Output is correct
46 Correct 228 ms 13564 KB Output is correct
47 Correct 2704 ms 17492 KB Output is correct
48 Correct 3091 ms 13852 KB Output is correct
49 Correct 3761 ms 14412 KB Output is correct
50 Correct 1730 ms 19264 KB Output is correct