Submission #156969

#	Time	Username	Problem	Language	Result	Execution time	Memory
156969		youngyojun	Fibonacci representations (CEOI18_fib)	C++11	100 / 100	654 ms	14980 KiB

fib

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
const int MOD = 1000000007;
 
struct MAT {
	MAT(int a = 1, int b = 0, int c = 0, int d = 1)
		: a(a), b(b), c(c), d(d) {}
	int a, b, c, d;
 
	void init() { a = d = 1; b = c = 0; }
	MAT operator * (const MAT &t) const {
		return MAT((ll(a)*t.a + ll(b)*t.c)%MOD, (ll(a)*t.b + ll(b)*t.d)%MOD
				 , (ll(c)*t.a + ll(d)*t.c)%MOD, (ll(c)*t.b + ll(d)*t.d)%MOD);
	}
	void cal(int ps, int pe, int s, int e) {
		if(e < 0) return;
		if(ps < 0) { init(); return; }
		int l = s-pe-1, ct = (e-s)>>1;
		a = (l+1)>>1; b = l>>1;
		c = (ll(ct)*((l+1)>>1) + 1) % MOD;
		d = (ll(ct)*(l>>1) + 1) % MOD;
	}
};

struct NOD {
	NOD(int si, int ei)
		: p(0), l(0), r(0), si(si), ei(ei) {}
	NOD *p, *l, *r;
	MAT dt, pd;
	int si, ei;

	void upd() {
		pd.init();
		if(l) pd = l->pd;
		pd = dt * pd;
		if(r) pd = r->pd * pd;
	}
	void rot() {
		NOD *c = p, *g = p->p;
		if(this == p->l) {
			p->l = r;
			if(r) r->p = p;
			r = p;
		} else {
			p->r = l;
			if(l) l->p = p;
			l = p;
		}
		p->p = this; p = g;
		if(g) (g->l == c ? g->l : g->r) = this;
		c->upd(); upd();
	}

	void cal(NOD *x) {
		dt.cal(x->si, x->ei, si, ei);
		upd();
	}
};

struct SPT {
	NOD *rt;

	void init() {
		rt = new NOD(-INF, -INF);
		rt->r = new NOD(INF, -1);
		rt->r->p = rt;
	}

	NOD* splay(NOD *x) {
		for(NOD *g; x->p;) {
			if(!(g = x->p->p)) {
				x->rot();
				break;
			}
			((g->l == x->p) == (x->p->l == x) ? x->p : x)->rot();
			x->rot();
		}
		return rt = x;
	}

	NOD* find(int K) {
		NOD *x = rt, *pv, *ret = 0;
		for(; x;) {
			pv = x;
			if(K <= x->si) {
				if(!ret || x->si < ret->si) ret = x;
				x = x->l;
			} else x = x->r;
		}
		splay(pv);
		return splay(ret);
	}

	NOD* prev(NOD *x) {
		if(!x->l) {
			for(; x->p->l == x;) x = x->p;
			return splay(x->p);
		}
		x = x->l;
		for(; x->r;) x = x->r;
		return splay(x);
	}
	NOD* next(NOD *x) {
		if(!x->r) {
			for(; x->p->r == x;) x = x->p;
			return splay(x->p);
		}
		x = x->r;
		for(; x->l;) x = x->l;
		return splay(x);
	}

	void pop(NOD *x) {
		splay(x);
		NOD *l = x->l, *r = x->r;
		delete x; x = 0;
		l->p = r->p = 0; rt = l;
		for(x = r; x->l;) x = x->l;
		for(; l->r;) l = l->r;
		x->cal(l);
		for(NOD *p = x; p; p = p->p) p->upd();
		l->r = r; r->p = l;
		for(; l; l = l->p) l->upd();
		splay(x);
	}
	void pop(int si, int ei) { pop(find(si)); }

	NOD* push(int si, int ei) {
		find(ei+1);
		NOD *x = new NOD(si, ei), *l = rt->l;
		rt->l = 0; x->l = l; l->p = x;
		x->r = rt; rt->p = x;
		rt->cal(x);
		for(; l->r;) l = l->r;
		x->cal(l);
		for(NOD *p = l; p; p = p->p) p->upd();
		splay(l);
		return splay(x);
	}

	MAT get() { return rt->pd; }
} spt;

const int MAXN = 100005;

set<pii> CH;

set<pii>::iterator get(int X) { return prev(CH.upper_bound({X, INF})); }
bool has(int X) {
	auto it = CH.upper_bound({X, INF});
	if(CH.begin() == it) return false;
	int s, e; tie(s, e) = *prev(it);
	return s <= X && X <= e && (s&1) == (X&1);
}

void insert(int s, int e) {
	bool flag = CH.insert({s, e}).second;
	if(flag) spt.push(s, e);
}
void erase(set<pii>::iterator it) {
	spt.pop(it->first, it->second);
	CH.erase(it);
}

void push(int X) {
	if(X < 1) return;
	if(1 == X) X = 2;
	if(!has(X)) {
		if(has(X-1) && !has(X+1)) {
			auto it = get(X-1);
			int s, e; tie(s, e) = *it;
			erase(it);
			e -= 2;
			if(s <= e) insert(s, e);
			push(X+1);
			return;
		}
		if(!has(X-1) && has(X+1)) {
			auto it = get(X+1);
			int s, e; tie(s, e) = *it;
			erase(it);
			push(e+1);
			return;
		}
		if(has(X-1) && has(X+1)) {
			auto it = get(X);
			int s, e; tie(s, e) = *it;
			erase(it);
			insert(s, X-1);
			push(e+1);
			return;
		}
		int s = X, e = X;
		if(has(X-2)) {
			auto it = get(X-2);
			int p, q; tie(p, q) = *it;
			erase(it);
			s = p;
		}
		if(has(X+2)) {
			auto it = get(X+2);
			int p, q; tie(p, q) = *it;
			erase(it);
			e = q;
		}
		insert(s, e);
		return;
	}

	auto it = get(X);
	int s, e; tie(s, e) = *it;
	erase(it);
	if(s+1 < X) insert(s+1, X-1);
	push(e+1);
	push(s-2);
}


int N;

ll getAns() {
	if(CH.empty()) return 0;
	MAT mat = spt.get();
	int s, e; tie(s, e) = *CH.begin();
	ll a = 0, b;
	if(1 < s-2) a = (ll(s-4)/2 + 1) % MOD;
	b = (1 + ll(s-2)/2 * ((e-s)/2)) % MOD;

	ll ret = a*mat.a % MOD;
	ret += b*mat.b % MOD;
	ret += a*mat.c % MOD;
	ret += b*mat.d % MOD;
	return ret % MOD;
}

int main() {
	ios::sync_with_stdio(false);

	spt.init();
	cin >> N;
	for(int i = 0; i < N; i++) {
		int x;
		cin >> x;
		push(x+1);
		printf("%lld\n", getAns());
	}
	return 0;
}

Compilation message (stderr)

fib.cpp: In function 'void insert(int, int)':
fib.cpp:100:8: warning: 'pv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   splay(pv);
   ~~~~~^~~~
fib.cpp:92:17: note: 'pv' was declared here
   NOD *x = rt, *pv, *ret = 0;
                 ^~
fib.cpp: In function 'void erase(std::set<std::pair<int, int> >::iterator)':
fib.cpp:100:8: warning: 'pv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   splay(pv);
   ~~~~~^~~~
fib.cpp:92:17: note: 'pv' was declared here
   NOD *x = rt, *pv, *ret = 0;
                 ^~

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