Submission #133892

#	Time	Username	Problem	Language	Result	Execution time	Memory
133892		sebinkim	Fibonacci representations (CEOI18_fib)	C++14	40 / 100	4013 ms	1736 KiB

fib

#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 + 1, x);
			ll x1 = it -> first - 1, x2 = it -> second;
			erase(it); if(p.first < p.second) insert(p);
			if(x1 >= 0) insert(t, max(x1, 1ll)); insert(t, x2);
		}
		else{
			pll p(it -> first, min(it -> second - 2, x));
			x = max(it -> second, x + 1);
			erase(it); if(p.first < p.second) insert(p);
			insert(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);
		insert(i, x);
		
//		for(pll t: S) printf("[%lld %lld] ", t.first, t.second); puts("");
		
		d0 = 0; d1 = 1; lt = 0;
		for(pll t: S){
			d = t.first + 1 - lt; l = (t.second - t.first) / 2;
			_d0 = (d / 2 * d0 + (d - 1) / 2 * d1) % mod;
			_d1 = (d0 + d1 + _d0 * (l - 1)) % mod;
			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:36:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(x1 >= 0) insert(t, max(x1, 1ll)); insert(t, x2);
    ^~
fib.cpp:36:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(x1 >= 0) insert(t, max(x1, 1ll)); insert(t, x2);
                                         ^~~~~~
fib.cpp: In function 'int main()':
fib.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
fib.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35