fork download
copy 
  1. /*
  2.  * Kamil Debowski
  3.  * O(n log(n)), the intended solution.
  4.  * Finds all changes of intervals offline and then builds a segment tree over them.
  5.  * No BST.
  6.  */
  7.  
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. const int INF = 1e9 + 1000; // must be bigger than max(A[i]) + log(n)
  11. const int mod = 1e9 + 7;
  12.  
  13. set<pair<int,int>> intervals; // pairs of indices (A, B) such that A,A+2,A+4,...,B are all 1's
  14. vector<vector<pair<int,int>>> events;
  15. int current_time;
  16.  
  17. void add_if_not_empty(int a, int b) {
  18. 	assert((b - a) % 2 == 0);
  19. 	if(a <= b) {
  20. 		assert(0 <= a && b < INF);
  21. 		events[current_time].push_back({a, b});
  22. 		intervals.insert({a, b});
  23. 	}
  24. }
  25.  
  26. void erase(set<pair<int,int>> :: iterator it) {
  27. 	events[current_time].push_back({it -> first, it -> second});
  28. 	intervals.erase(it);
  29. }
  30.  
  31. void add_outside(const int x) {
  32. 	auto R = intervals.upper_bound({x, INF});
  33. 	if(x + 1 == R -> first) { // just before the interval R
  34. 		// the whole interval is compressed to R->second+1
  35. 		const int new_value = R -> second + 1;
  36. 		erase(R);
  37. 		add_outside(new_value);
  38. 		return;
  39. 	}
  40. 	auto L = prev(R);
  41. 	if(L -> second + 1 == x) { // just after the interval L
  42. 		// erase the last element of L
  43. 		add_if_not_empty(L -> first, L -> second - 2);
  44. 		erase(L);
  45. 		add_outside(x + 1);
  46. 		return;
  47. 	}
  48. 	pair<int,int> new_interval{x, x};
  49. 	if(x + 2 == R -> first) {
  50. 		new_interval.second = R -> second;
  51. 		erase(R);
  52. 	}
  53. 	if(L -> second + 2 == x) {
  54. 		new_interval.first = L -> first;
  55. 		erase(L);
  56. 	}
  57. 	add_if_not_empty(new_interval.first, new_interval.second);
  58. }
  59.  
  60. void add_possibly_inside(const int x) {
  61. 	auto it = intervals.upper_bound({x, INF});
  62. 	it--;
  63. 	if(!(it -> first <= x && x <= it -> second)) {
  64. 		add_outside(x);
  65. 		return;
  66. 	}
  67. 	// now we know that 'x' is inside the interval
  68. 	assert(0 <= it -> first && it -> second < INF);
  69. 	if(it -> first % 2 != x % 2) {
  70. 		/*
  71. 		 *   ...0001010101010100...
  72. 		 * +            1
  73. 		 * = ...0001010100000010...
  74. 		 */
  75. 		add_if_not_empty(it -> first, x - 1);
  76. 		const int new_value = it -> second + 1;
  77. 		erase(it);
  78. 		add_outside(new_value);
  79. 		return;
  80. 	}
  81. 	/*
  82. 	 *   ...0001010101010100...
  83. 	 * +           1
  84. 	 * = ...0100101011010100...
  85. 	 * = ...0100101000000010...
  86. 	 */
  87. 	const vector<int> new_values{it -> first - 2, it -> second + 1};
  88. 	add_if_not_empty(it -> first + 1, x - 1);
  89. 	erase(it);
  90. 	for(int a : new_values) {
  91. 		if(a == -2) continue; // Fib[-2] = 0
  92. 		if(a == -1) a = 0; // Fib[-1] = Fib[0]
  93. 		add_outside(a);
  94. 	}
  95. }
  96.  
  97. struct M {
  98. 	#define REP(i) for(int i = 0; i < 2; ++i)
  99. 	int m[2][2]; // m[A][B] = m[rightmost bit can be not-changed][leftmost bit...]
  100. 	int * operator [] (int i) { return m[i]; }
  101. 	const int * operator [] (int i) const { return m[i]; }
  102. 	M() { REP(i) REP(j) m[i][j] = 0; }
  103. 	M operator * (const M & b) const {
  104. 		M r;
  105. 		REP(i) REP(j) REP(k)
  106. 			r[i][k] = (r[i][k] + (long long) m[i][j] * b[j][k]) % mod;
  107. 		return r;
  108. 	}
  109. 	#undef REP
  110. };
  111.  
  112. struct S {
  113. 	bool exists = false;
  114. 	M m;
  115. 	int low, high;
  116. 	void init(pair<int,int> p) {
  117. 		low = p.first, high = p.second;
  118. 		int size = (high - low) / 2 + 1;
  119. 		m[0][0] = 1;
  120. 		m[0][1] = 0;
  121. 		m[1][0] = size - 1;
  122. 		m[1][1] = 1;
  123. 	}
  124. 	void merge(const S & A, const S & B) {
  125. 		exists = A.exists || B.exists;
  126. 		if(!A.exists) {
  127. 			*this = B;
  128. 			return;
  129. 		}
  130. 		if(!B.exists) {
  131. 			*this = A;
  132. 			return;
  133. 		}
  134. 		low = A.low;
  135. 		high = B.high;
  136. 		const int dist = B.low - A.high;
  137. 		//~ assert(dist >= 3);
  138. 		M mid;
  139. 		if(dist % 2 == 0) {
  140. 			mid[0][0] = 1;
  141. 			mid[1][0] = 1;
  142. 		}
  143. 		mid[0][1] = mid[1][1] = max(0, (dist - 1) / 2);
  144. 		mid[1][1] = (mid[1][1] + 1) % mod;
  145. 		m = (B.m * mid) * A.m;
  146. 	}
  147. };
  148.  
  149. int main() {
  150. 	int n;
  151. 	scanf("%d", &n);
  152. 	events.resize(n);
  153. 	intervals.insert({-4, -4});
  154. 	intervals.insert({INF, INF}); // to simplify the implementation
  155. 	for(current_time = 0; current_time < n; ++current_time) {
  156. 		int ai;
  157. 		scanf("%d", &ai);
  158. 		--ai;
  159. 		add_possibly_inside(ai);
  160. 	}
  161.  
  162. 	vector<pair<int,int>> all;
  163. 	for(const vector<pair<int,int>> & vec : events)
  164. 		for(const pair<int,int> & p : vec)
  165. 			all.push_back(p);
  166. 	sort(all.begin(), all.end());
  167. 	all.resize(unique(all.begin(),all.end()) - all.begin());
  168.  
  169. 	int pot = 1;
  170. 	while(pot < (int) all.size()) pot *= 2;
  171. 	vector<S> tr(2 * pot);
  172. 	for(int i = 0; i < (int) all.size(); ++i)
  173. 		tr[pot+i].init(all[i]);
  174. 	S START;
  175. 	START.init({-1, -1});
  176. 	START.exists = true;
  177. 	for(current_time = 0; current_time < n; ++current_time) {
  178. 		for(pair<int,int> p : events[current_time]) {
  179. 			int i = lower_bound(all.begin(), all.end(), p) - all.begin();
  180. 			tr[pot+i].exists = !tr[pot+i].exists;
  181. 			for(int x = (pot + i) / 2; x >= 1; x /= 2)
  182. 				tr[x].merge(tr[2*x], tr[2*x+1]);
  183. 		}
  184. 		S total;
  185. 		total.merge(START, tr[1]);
  186. 		printf("%d\n", total.m[1][1]);
  187. 	}
  188. }
  189.  
Runtime error #stdin #stdout #stderr 0s 4468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:20: void add_if_not_empty(int, int): Assertion `0 <= a && b < INF' failed.
https://ideone.com/gZYsM4
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!