fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef unsigned long long int64;
  6.  
  7. const int N = 500500;
  8. const int64 base = 500519;
  9. const int64 base2 = 502181;
  10.  
  11. int n, m, res;
  12. int64 pw[N];
  13. int64 pw2[N];
  14. pair < int, int > a[N];
  15.  
  16. int lab[N]; /// DSU
  17. vector < list < int > > comp;
  18.  
  19. int par(int u){
  20. 	return (lab[u] < 0 ? u : lab[u] = par(lab[u]));
  21. }
  22.  
  23. #define mid ((l + r) >> 1)
  24.  
  25. int pos[N];
  26.  
  27. struct node_t{
  28. 	int len;
  29. 	pair < int64, int64 > hs;
  30.  
  31. 	node_t operator+(const node_t &other)const{
  32. 		node_t ret;
  33. 		ret.len = len + other.len;
  34. 		ret.hs.first = hs.first * pw[other.len] + other.hs.first;
  35. 		ret.hs.second = hs.second * pw2[other.len] + other.hs.second;
  36. 		return ret;
  37. 	}
  38.  
  39. 	bool operator ==(const node_t &other)const{
  40. 		return (len == other.len && hs == other.hs);
  41. 	}
  42. };
  43.  
  44. node_t it[N << 2];
  45. node_t rev[N << 2];
  46.  
  47. void build(int x, int l, int r){
  48. 	if(l == r){
  49. 		pos[r] = x;
  50. 		it[x] = rev[x] = {1, {par(r), par(r)}};
  51. 		return;
  52. 	}
  53. 	build(x + x, l, mid);
  54. 	build(x + x + 1, mid + 1, r);
  55. 	it[x] = it[x + x] + it[x + x + 1];
  56. 	rev[x] = rev[x + x + 1] + rev[x + x];
  57. }
  58.  
  59. void upd(int x, int c){
  60. 	int cur = pos[x];
  61. 	it[cur] = rev[cur] = {1, {c, c}};
  62. 	cur /= 2;
  63.  
  64. 	while(cur){
  65. 		it[cur] = it[cur + cur] + it[cur + cur + 1];
  66. 		rev[cur] = rev[cur + cur + 1] + rev[cur + cur];
  67. 		cur /= 2;
  68. 	}
  69. }
  70.  
  71. node_t query(int x, int l, int r, int u, int v){
  72. 	if(l > v || r < u) return {0, {0, 0}};
  73. 	if(l >= u && r <= v) return it[x];
  74. 	node_t ans =  query(x + x , l, mid, u, v) + query(x + x + 1, mid + 1, r, u, v);
  75. 	return ans;
  76. }
  77.  
  78. node_t queryRev(int x, int l, int r, int u, int v){
  79. 	if(l > v || r < u) return {0, {0, 0}};
  80. 	if(l >= u && r <= v) return rev[x];
  81. 	return queryRev(x + x + 1, mid + 1, r, u, v) + query(x + x, l, mid, u, v);
  82. }
  83.  
  84. #undef mid
  85.  
  86. void join(int u, int v, bool update = false){
  87. 	u = par(u); v = par(v);
  88. 	if(u == v) return;
  89. 	if(lab[u] > lab[v]) swap(u, v);
  90. 	lab[u] += lab[v];
  91. 	lab[v] = u;
  92. 	--res;
  93. 	for(int x : comp[v]) {
  94. 		if(update) upd(x, u);
  95. 		comp[u].push_back(x);
  96. 	}
  97. 	return comp[v].clear();
  98. }
  99.  
  100. bool cmp(pair < int, int > u, pair < int, int > v){
  101. 	return (u.second - u.first) > (v.second - v.first);
  102. }
  103.  
  104. int main(){
  105.  
  106. 	pw[0] = pw2[0] = 1;
  107.  
  108. 	scanf("%d", &n);
  109. 	for(int i = 1; i <= n; ++i){
  110. 		pw[i] = pw[i - 1] * base;
  111. 		pw2[i] = pw2[i - 1] * base2;
  112. 	}
  113.  
  114. 	scanf("%d", &m);
  115. 	for(int i = 1; i <= m; ++i){
  116. 		scanf("%d%d", &a[i].first, &a[i].second);
  117. 	}
  118.  
  119. 	comp.resize(n + 1);
  120.  
  121. 	memset(lab, -1, sizeof lab);
  122. 	for(int i = 1; i <= n; ++i){
  123. 		comp[i].push_back(i);
  124. 	}
  125.  
  126. 	sort(a + 1, a + m + 1, cmp);
  127.  
  128. 	res = n;
  129.  
  130. 	for(int i = m; i >= 1; --i){
  131.  
  132. 		if(a[i].second - a[i].first > 1000) break;
  133. 		int mid = (a[i].second + a[i].first) / 2;
  134. 		for(int x = a[i].first; x <= mid; ++x){
  135. 			int v = a[i].second - x + a[i].first;
  136. 			join(x, v);
  137. 		}
  138. 		m = i - 1;		
  139. 	}
  140.  
  141. 	int start = 1;
  142.  
  143. 	for(int i = 1; i <= min(m, 20); ++i){
  144.  
  145. 		int mid = (a[i].second + a[i].first) / 2;
  146. 		for(int x = a[i].first; x <= mid; ++x){
  147. 			int v = a[i].second - x + a[i].first;
  148. 			join(x, v);
  149. 		}
  150. 		start = i + 1;
  151. 	}
  152.  
  153. 	build(1, 1, n);
  154.  
  155. 	for(int i = start; i <= m; ++i){
  156. 		int l = a[i].first;
  157. 		int r = a[i].second;
  158. 		int u = (l + r) >> 1;
  159. 		int v = u + (l % 2 != r % 2);
  160.  
  161. 		while(l < r){
  162. 			if(query(1, 1, n, l, u) == queryRev(1, 1, n, v, r)) break;
  163. 			int low = 0, high = u - l, ans = -1;
  164.  
  165. 			while(low <= high){
  166. 				int mid = (low + high) >> 1;
  167. 				if(query(1, 1, n, l, l + mid) == query(1, 1, n, r - mid, r)){
  168. 					low = mid + 1;
  169. 				}
  170. 				else{
  171. 					high = mid - 1;
  172. 					ans = mid;
  173. 				}
  174. 			}
  175. 			join(l + ans, r - ans);
  176. 			l += ans + 1;
  177. 			r -= ans + 1;
  178. 		}
  179. 	}
  180.  
  181. 	cout << res;
  182.  
  183. 	return 0;
  184. }
Time limit exceeded #stdin #stdout 5s 8003584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/APkbpK
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!