oj.uz

Submission #128645

# Submission time Handle Problem Language Result Execution time Memory
128645 2019-07-11T07:56:26 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
20 / 100
 283 ms 29104 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;

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], E[SQRN*2];
	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(; S[i] < X; i++);
		return i;
	}
	void push(int s, int e) {
		int i = 0; for(; S[i] < s; i++);
		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 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[n];
				E[n] = buk[i].E[n];
				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++);
		//printf("PUSH %d %d / %d\n", s, e, i);
		if(!buk[i].n) {
			int ps, pe; findPrev(i, 0, ps, pe);
			buk[i].pushFront(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

# Verdict Execution time Memory Grader output
1 Correct 11 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 11 ms 11772 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 11 ms 11772 KB Output is correct
7 Correct 12 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 37 ms 23544 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

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 11 ms 11772 KB Output is correct
7 Correct 12 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 37 ms 23544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11768 KB Output is correct
2 Runtime error 283 ms 29104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 11 ms 11772 KB Output is correct
7 Correct 12 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 37 ms 23544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -