Submission #128969

#TimeUsernameProblemLanguageResultExecution timeMemory
128969youngyojunFibonacci representations (CEOI18_fib)C++11
50 / 100
1290 ms14280 KiB
#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) {} 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); } }; const int MAXN = 100005; const int SQRN = 250; struct BUK { MAT mat[SQRN*3+5], matProd; int S[SQRN*3+5], E[SQRN*3+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; 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; } 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++); 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) { 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) { 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) { 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; } 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(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) 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; 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()); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...