| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 899397 | math_rabbit_1028 | Fibonacci representations (CEOI18_fib) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> pii;ll MOD = 1e9 + 7; int n, arr[101010];struct Matrixseg{ struct Matrix { ll a, b, c, d; } tree[404040]; Matrix E; Matrix get_mat(int d) { assert(d >= 0); if (d == 0) return E; if (d % 2 == 0) return {d/2 + 1, MOD-1, 1, 0}; else return {d/2 + 1, 0, 1, 0}; } Matrix mat_pow(Matrix A, int p) { if (p == 0) return E; Matrix ret = mat_pow(A, p/2); ret = prod(ret, ret); if (p%2 == 0) return ret; else return prod(ret, A); } Matrix prod(Matrix A, Matrix B) { Matrix ret; ret.a = (A.a * B.a + A.b * B.c) % MOD; ret.b = (A.a * B.b + A.b * B.d) % MOD; ret.c = (A.c * B.a + A.d * B.c) % MOD; ret.d = (A.c * B.b + A.d * B.d) % MOD; return ret; } void init(int v, int st, int ed) { if (st == ed) { tree[v] = E; return; } int mid = (st + ed) / 2; init(2 * v, st, mid); init(2 * v + 1, mid + 1, ed); tree[v] = prod(tree[2 * v + 1], tree[2 * v]); } void upd(int v, int st, int ed, int idx, Matrix mat) { if (st == idx && ed == idx) { tree[v] = mat; return; } if (st > idx || ed < idx) return; int mid = (st + ed) / 2; upd(2 * v, st, mid, idx, mat); upd(2 * v + 1, mid + 1, ed, idx, mat); tree[v] = prod(tree[2 * v + 1], tree[2 * v]); } Matrix get(int v, int st, int ed, int lt, int rt) { if (lt <= st && ed <= rt) return tree[v]; if (st > rt || lt > ed) return E; int mid = (st + ed) / 2; return prod(get(2 * v + 1, mid + 1, ed, lt, rt), get(2 * v, st, mid, lt, rt)); }} seg; set<pii> s;set<int> nums;vector<int> vec;int m; int get_idx(int val) { return lower_bound(vec.begin(), vec.end(), val) - vec.begin() + 1;} void _modify(set<pii>::iterator it, pii temp) { auto up = it, dn = it; up++; seg.upd(1, 1, m, get_idx(it->first), seg.E); seg.upd(1, 1, m, get_idx(it->second), seg.E); int bot = 0; if (it != s.begin()) { dn--; bot = dn->second; } seg.upd(1, 1, m, get_idx(temp.first), seg.get_mat(temp.first - bot)); if (temp.first != temp.second) seg.upd(1, 1, m, get_idx(temp.second), seg.mat_pow(seg.get_mat(2), (temp.second - temp.first) / 2)); if (up != s.end()) { seg.upd(1, 1, m, get_idx(up->first), seg.get_mat(up->first - temp.second)); }} void modify(set<pii>::iterator *it, pii temp) { if (vec.size() > 0) _modify(*it, temp); s.erase(*it); *it = s.insert(temp).first; nums.insert(temp.first); nums.insert(temp.second);} void _add(pii temp) { auto up = s.lower_bound(temp), dn = up; int bot = 0; if (up != s.begin()) { dn--; bot = dn->second; } seg.upd(1, 1, m, get_idx(temp.first), seg.get_mat(temp.first - bot)); if (temp.first != temp.second) seg.upd(1, 1, m, get_idx(temp.second), seg.mat_pow(seg.get_mat(2), (temp.second - temp.first) / 2)); if (up != s.end()) { seg.upd(1, 1, m, get_idx(up->first), seg.get_mat(up->first - temp.second)); }} set<pii>::iterator add(pii temp) { if (vec.size() > 0) _add(temp); nums.insert(temp.first); nums.insert(temp.second); return s.insert(temp).first;} void _rem(set<pii>::iterator it) { auto up = it, dn = it; up++; seg.upd(1, 1, m, get_idx(it->first), seg.E); seg.upd(1, 1, m, get_idx(it->second), seg.E); int bot = 0; if (it != s.begin()) { dn--; bot = dn->second; } if (up != s.end()) { seg.upd(1, 1, m, get_idx(up->first), seg.get_mat(up->first - bot)); }} set<pii>::iterator rem(set<pii>::iterator it) { if (vec.size() > 0) _rem(it); return s.erase(it);} int main() { ios_base::sync_with_stdio(false); cin.tie(0); seg.E = {1, 0, 0, 1}; cin >> n; for (int i = 1; i <= n; i++) cin >> arr[i]; for (int i = 1; i <= n; i++) { do { auto up = s.lower_bound({arr[i]+1, 0}), dn = up; if (up != s.begin()) dn--; if (up != s.begin() && dn->first <= arr[i] && arr[i] <= dn->second) { if (dn->first%2 == arr[i]%2) { int val = dn->second + 1; if (up != s.end() && val+2 == up->first) modify(&up, {val, up->second}); else up = add({val, val}); val = dn->first-2; modify(&dn, {dn->first+1, arr[i]-1}); if (dn->first > dn->second) dn = rem(dn); if (up->first == dn->second+2) { pii val = {dn->first, up->second}; rem(up); rem(dn); add(val); } if (dn == s.begin()) { if (val != -1) { up = add({max(val, 1), max(val, 1)}); up++; if (up->first == max(val, 1)+2) { modify(&up, {max(val, 1), up->second}); up = rem(--up); } } } else { dn--; if (dn->second == val-2) { modify(&dn, {dn->first, val}); } else if (dn->second == val-1) { if (dn->first == dn->second) dn = --rem(dn); else modify(&dn, {dn->first, dn->second-2}); up = add({val+1, val+1}); up++; if (up->first == val+3) { modify(&up, {val+1, up->second}); up = rem(--up); } } else { add({val, val}); } } } else { int val = dn->second + 1; if (up != s.end() && val+2 == up->first) modify(&up, {val, up->second}); else add({val, val}); modify(&dn, {dn->first, arr[i]-1}); } continue; } if (up != s.end() && up->first == arr[i]+1) { int val = up->second + 1; up = rem(up); if (up != s.end() && up->first == val+2) modify(&up, {val, up->second}); else add({val, val}); continue; } if (up != s.begin() && dn->second == arr[i]-1) { if (dn->second-2 < dn->first) dn = --rem(dn); else modify(&dn, {dn->first, dn->second-2}); if (up != s.end() && up->first == arr[i]+2) { int val = up->second + 1; up = rem(up); if (up != s.end() && up->first == val+2) modify(&up, {val, up->second}); else add({val, val}); } else if (up != s.end() && up->first == arr[i]+3) modify(&up, {arr[i]+1, up->second}); else add({arr[i]+1, arr[i]+1}); continue; } if (up != s.begin() && dn->second == arr[i]-2) { if (up != s.end() && up->first == arr[i]+2) { pii val = {dn->first, up->second}; rem(up); rem(dn); add(val); } else modify(&dn, {dn->first, arr[i]}); continue; } if (up != s.end() && up->first == arr[i]+2) { modify(&up, {arr[i], up->second}); continue; } add({arr[i], arr[i]}); } while(0); } for (auto iter = nums.begin(); iter != nums.end(); iter++) { vec.push_back(*iter); } m = vec.size(); seg.init(1, 1, m); s.clear(); for (int i = 1; i <= n; i++) { do { auto up = s.lower_bound({arr[i]+1, 0}), dn = up; if (up != s.begin()) dn--; if (up != s.begin() && dn->first <= arr[i] && arr[i] <= dn->second) { if (dn->first%2 == arr[i]%2) { int val = dn->second + 1; if (up != s.end() && val+2 == up->first) modify(&up, {val, up->second}); else up = add({val, val}); val = dn->first-2; modify(&dn, {dn->first+1, arr[i]-1}); if (dn->first > dn->second) dn = rem(dn); if (up->first == dn->second+2) { pii val = {dn->first, up->second}; rem(up); rem(dn); add(val); } if (dn == s.begin()) { if (val != -1) { up = add({max(val, 1), max(val, 1)}); up++; if (up->first == max(val, 1)+2) { modify(&up, {max(val, 1), up->second}); up = rem(--up); } } } else { dn--; if (dn->second == val-2) { modify(&dn, {dn->first, val}); } else if (dn->second == val-1) { if (dn->first == dn->second) dn = --rem(dn); else modify(&dn, {dn->first, dn->second-2}); up = add({val+1, val+1}); up++; if (up->first == val+3) { modify(&up, {val+1, up->second}); up = rem(--up); } } else { add({val, val}); } } } else { int val = dn->second + 1; if (up != s.end() && val+2 == up->first) modify(&up, {val, up->second}); else add({val, val}); modify(&dn, {dn->first, arr[i]-1}); } continue; } if (up != s.end() && up->first == arr[i]+1) { int val = up->second + 1; up = rem(up); if (up != s.end() && up->first == val+2) modify(&up, {val, up->second}); else add({val, val}); continue; } if (up != s.begin() && dn->second == arr[i]-1) { if (dn->second-2 < dn->first) dn = --rem(dn); else modify(&dn, {dn->first, dn->second-2}); if (up != s.end() && up->first == arr[i]+2) { int val = up->second + 1; up = rem(up); if (up != s.end() && up->first == val+2) modify(&up, {val, up->second}); else add({val, val}); } else if (up != s.end() && up->first == arr[i]+3) modify(&up, {arr[i]+1, up->second}); else add({arr[i]+1, arr[i]+1}); continue; } if (up != s.begin() && dn->second == arr[i]-2) { if (up != s.end() && up->first == arr[i]+2) { pii val = {dn->first, up->second}; rem(up); rem(dn); add(val); } else modify(&dn, {dn->first, arr[i]}); continue; } if (up != s.end() && up->first == arr[i]+2) { modify(&up, {arr[i], up->second}); continue; } add({arr[i], arr[i]}); } while(0); Matrixseg::Matrix ans = seg.get(1, 1, m, 1, m); cout << (ans.a + ans.b) % MOD << "\n"; } return 0;}