Submission #134304

#TimeUsernameProblemLanguageResultExecution timeMemory
134304sebinkimFibonacci representations (CEOI18_fib)C++14
100 / 100
675 ms81572 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <ll, ll> pll; const ll mod = 1e9 + 7; struct matrix{ ll aa, ab, ba, bb; matrix() : aa(1), ab(0), ba(0), bb(1) {} matrix(ll aa, ll ab, ll ba, ll bb) : aa(aa), ab(ab), ba(ba), bb(bb) {} matrix(ll x, ll d) { aa = x / 2 % mod; ab = (x - 1) / 2 % mod; ba = (aa * (d - 1) + 1) % mod; bb = (ab * (d - 1) + 1) % mod; } matrix operator * (matrix m) { return matrix((aa * m.aa + ab * m.ba) % mod, (aa * m.ab + ab * m.bb) % mod, (ba * m.aa + bb * m.ba) % mod, (ba * m.ab + bb * m.bb) % mod); } }; struct node{ ll d, l, r; matrix m; node() : d(0) {} node(pll p) : d((p.second - p.first) / 2), l(p.first + 1), r(p.second - 1) {} }; node operator + (node na, node nb) { if(!na.d) return nb; if(!nb.d) return na; node ret = na; ret.r = nb.r; matrix m(nb.l - na.r, nb.d); ret.m = nb.m * m * na.m; return ret; } struct segtree{ node T[1101010]; ll sz = 1 << 19; void update(ll p, pll v) { p += sz; if(T[p].d) T[p] = node(); else T[p] = node(v); for(p>>=1; p; p>>=1){ T[p] = T[p << 1] + T[p << 1 | 1]; } } ll getans() { matrix m = T[1].m * matrix(T[1].l, T[1].d); return (m.ab + m.bb) % mod; } }; segtree T; set <pll> S; vector <pll> X[101010]; vector <ll> Z; ll n; void insert(ll t, pll p) { Z.push_back(p.first); X[t].push_back(p); S.insert(p); } void erase(ll t, set <pll>::iterator it) { X[t].push_back(*it); S.erase(it); } void addval(ll t, ll x) { auto it = S.lower_bound(pll(x, 2e9)); if(it == S.begin() || prev(it) -> second < x){ pll p(x - 1, x + 1); if(it != S.begin() && prev(it) -> second + 1 == x){ p.first = prev(it) -> first; erase(t, prev(it)); } it = S.lower_bound(pll(x, 2e9)); if(it != S.end() && x + 1 == it -> first){ p.second = it -> second; erase(t, it); } insert(t, p); } else{ it = prev(it); if(it -> second - x & 1){ pll p(it -> first + 1, x); ll x1 = it -> first - 1, x2 = it -> second; erase(t, it); if(p.first < p.second) insert(t, p); if(x1 >= 0) addval(t, max(x1, 1ll)); addval(t, x2); } else{ pll p(it -> first, min(it -> second - 2, x)); x = max(it -> second, x + 1); erase(t, it); if(p.first < p.second) insert(t, p); addval(t, x); } } } int main() { ll i, x; ll d0, d1, lt, _d0, _d1, d, l; scanf("%lld", &n); for(i=0; i<n; i++){ scanf("%lld", &x); addval(i, x); } sort(Z.begin(), Z.end()); Z.erase(unique(Z.begin(), Z.end()), Z.end()); for(i=0; i<n; i++){ for(pll &t: X[i]){ x = lower_bound(Z.begin(), Z.end(), t.first) - Z.begin(); T.update(x, t); } printf("%lld\n", T.getans()); } return 0; }

Compilation message (stderr)

fib.cpp: In function 'void addval(ll, ll)':
fib.cpp:104:19: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   if(it -> second - x & 1){
      ~~~~~~~~~~~~~^~~
fib.cpp:108:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(x1 >= 0) addval(t, max(x1, 1ll)); addval(t, x2);
    ^~
fib.cpp:108:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(x1 >= 0) addval(t, max(x1, 1ll)); addval(t, x2);
                                         ^~~~~~
fib.cpp: In function 'int main()':
fib.cpp:122:5: warning: unused variable 'd0' [-Wunused-variable]
  ll d0, d1, lt, _d0, _d1, d, l;
     ^~
fib.cpp:122:9: warning: unused variable 'd1' [-Wunused-variable]
  ll d0, d1, lt, _d0, _d1, d, l;
         ^~
fib.cpp:122:13: warning: unused variable 'lt' [-Wunused-variable]
  ll d0, d1, lt, _d0, _d1, d, l;
             ^~
fib.cpp:122:17: warning: unused variable '_d0' [-Wunused-variable]
  ll d0, d1, lt, _d0, _d1, d, l;
                 ^~~
fib.cpp:122:22: warning: unused variable '_d1' [-Wunused-variable]
  ll d0, d1, lt, _d0, _d1, d, l;
                      ^~~
fib.cpp:122:27: warning: unused variable 'd' [-Wunused-variable]
  ll d0, d1, lt, _d0, _d1, d, l;
                           ^
fib.cpp:122:30: warning: unused variable 'l' [-Wunused-variable]
  ll d0, d1, lt, _d0, _d1, d, l;
                              ^
fib.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
fib.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~
#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...