Submission #134306

#	Time	Username	Problem	Language	Result	Execution time	Memory
134306		sebinkim	Fibonacci representations (CEOI18_fib)	C++14	100 / 100	584 ms	80512 KiB

fib

#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;
	
	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:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
fib.cpp:126: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: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 35 / 35