oj.uz

Submission #133896

# Submission time Handle Problem Language Result Execution time Memory
133896 2019-07-21T16:38:21 Z sebinkim Fibonacci representations (CEOI18_fib) C++14
50 / 100
 4000 ms 1788 KB 
#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, 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(prev(it));
		}
		it = S.lower_bound(pll(x, 2e9));
		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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Execution timed out 4016 ms 1788 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Execution timed out 4016 ms 1788 KB Time limit exceeded
26 Halted 0 ms 0 KB -