Submission #133871

#TimeUsernameProblemLanguageResultExecution timeMemory
133871sebinkimFibonacci representations (CEOI18_fib)C++14
15 / 100
4003 ms2048 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <ll, ll> pll; const ll mod = 1e9 + 7; set <pll> S; ll n; void erase(set <pll>::iterator it) { S.erase(it); } void insert(pll p) { S.insert(p); } void insert(ll t, ll x) { auto it = S.lower_bound(pll(x, 1e9)); 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(prev(it)); } it = S.lower_bound(pll(x, 1e9)); if(it != S.end() && x + 1 == it -> first){ p.second = it -> second; erase(it); } insert(p); } else{ it = prev(it); if(it -> second - x & 1){ pll p(it -> first, x - 1); ll x1 = it -> first - 1, x2 = it -> second; erase(it); insert(t, x2); if(p.first < p.second) insert(p); if(x1 > 0) insert(t, x1); } else{ pll p(it -> first, it -> second == x? x - 2: x); x = it -> second + 1; erase(it); insert(t, x); if(p.first < p.second) insert(p); } } } int main() { ll i, x; ll d0, d1, lt, _d0, _d1, l; scanf("%lld", &n); for(i=0; i<n; i++){ scanf("%lld", &x); insert(i, x); d0 = 0; d1 = 1; lt = 0; for(pll t: S){ l = t.first + 1 - lt; _d0 = ((l / 2) * d0 + (l - 1) / 2 * d1) % mod; _d1 = d1 + d0; d0 = _d0; d1 = _d1; lt = t.second - 1; } printf("%lld\n", (d0 + d1) % mod); } return 0; }

Compilation message (stderr)

fib.cpp: In function 'void insert(ll, ll)':
fib.cpp:32:19: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   if(it -> second - x & 1){
      ~~~~~~~~~~~~~^~~
fib.cpp: In function 'int main()':
fib.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
fib.cpp:56: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...