fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MOD = 1e9 + 7;
  6. const int N = 2010;
  7.  
  8. struct queue_max
  9. {
  10. 	deque<int> q;
  11. 	deque<int> w;
  12. 	int sum;
  13. 	int mx;
  14.  
  15. 	queue_max()
  16. 	{
  17. 		sum = 0;
  18. 		mx = 0;
  19. 		q.clear();
  20. 		w.clear();
  21. 	}
  22.  
  23. 	inline void init()
  24. 	{
  25. 		sum = 0;
  26. 		mx = 0;
  27. 		q.clear();
  28. 		w.clear();
  29. 	}
  30.  
  31. 	inline void add(int x, int ww)
  32. 	{
  33. 		while (!q.empty() && q.back() < x)
  34. 		{
  35. 			q.pop_back();
  36. 			w.pop_back();
  37. 		}
  38. 		if (q.empty())
  39. 		{
  40. 			q.push_back(x);
  41. 			w.push_back(ww);
  42. 			mx = x;
  43. 			sum = ww;
  44. 			return;
  45. 		}
  46. 		q.push_back(x);
  47. 		w.push_back(ww);
  48. 		if (x < mx) return;
  49. 		sum += ww;
  50. 		if (sum >= MOD) sum -= MOD;
  51. 	}
  52.  
  53. 	inline void del(int x, int ww)
  54. 	{
  55. 		if (q.front() != x) return;
  56. 		q.pop_front();
  57. 		w.pop_front();
  58. 		if (q.empty()) return;
  59. 		if (q.front() == mx)
  60. 		{
  61. 			sum -= ww;
  62. 			if (sum < 0) sum += MOD;
  63. 			return;
  64. 		}
  65. 		mx = q.front();
  66. 		sum = 0;
  67. 		for (int i = 0; i < (int)q.size(); i++)
  68. 		{
  69. 			if (q[i] != mx) break;
  70. 			sum += w[i];
  71. 			if (sum >= MOD) sum -= MOD;
  72. 		}
  73. 	}
  74. };
  75.  
  76. int par[N][N], rg[N][N], mx[N][N];
  77.  
  78. inline void init(int n, int m)
  79. {
  80. 	for (int i = 0; i < n; i++)
  81. 		for (int j = 0; j < m; j++)
  82. 			par[i][j] = j, rg[i][j] = 0, mx[i][j] = j + 1;	
  83. }
  84.  
  85. inline int find_set(int i, int j)
  86. {
  87. 	if (par[i][j] == j) return j;
  88. 	return (par[i][j] = find_set(i, par[i][j]));
  89. }
  90.  
  91. inline void merge_set(int i, int x1, int x2)
  92. {
  93. 	x1 = find_set(i, x1);
  94. 	x2 = find_set(i, x2);
  95. 	if (x1 == x2) return;
  96. 	if (rg[i][x1] > rg[i][x2]) swap(x1, x2);
  97. 	mx[i][x2] = max(mx[i][x2], mx[i][x1]);
  98. 	par[i][x1] = x2;
  99. 	if (rg[i][x1] == rg[i][x2]) rg[i][x2]++;
  100. }
  101.  
  102. inline int gett(int i, int j)
  103. {
  104. 	return mx[i][find_set(i, j)];
  105. }
  106.  
  107. queue_max vx[N], vy[N];
  108. int n, m, q, l[N][N], u[N][N], dp[N][N], kol[N][N];
  109. vector<tuple<int, int, int> > a[N], b[N];
  110.  
  111. inline void solve()
  112. {
  113. 	cin >> n >> m >> q;
  114. 	for (int i = 0; i < n; i++)
  115. 		for (int j = 0; j < m; j++)
  116. 			l[i][j] = -1, u[i][j] = -1;
  117. 	for (int i = 0; i < m; i++)
  118. 		a[i].clear();
  119. 	for (int i = 0; i < n; i++)
  120. 		b[i].clear();
  121. 	for (int i = 0; i < q; i++)
  122. 	{
  123. 		int x1, y1, x2, y2;
  124. 		cin >> x1 >> y1 >> x2 >> y2;
  125. 		x1--, x2--, y1--, y2--;
  126. 		if (x1 == x2 || y1 == y2) continue;
  127. 		x1++, y1++;
  128. 		a[y1].push_back(make_tuple(x1, x2, y2));
  129. 		b[x1].push_back(make_tuple(y1, y2, x2));
  130. 	}                
  131. 	init(m, n);                       
  132. 	for (int j = 0; j < m; j++)
  133. 		for (tuple<int, int, int> t : a[j])
  134. 		{
  135. 			int to = get<2>(t);
  136. 			int s = get<0>(t);
  137. 			int f = get<1>(t);
  138. 			for (int x = to; x >= j; x--)
  139. 			{
  140. 				if (l[s][x] != -1 && gett(x, s) > f) break;
  141. 				int p = s;
  142. 				while (p <= f)
  143. 				{
  144. 					if (l[p][x] == -1) 
  145. 					{
  146. 						l[p][x] = (j - 1);
  147. 						if (p > 0 && l[p - 1][x] != -1) merge_set(x, p - 1, p);
  148. 						if (p < n - 1 && l[p + 1][x] != -1) merge_set(x, p, p + 1); 
  149. 					}
  150. 					p = gett(x, p);
  151. 				}			
  152. 			}
  153. 		}                              
  154. 	init(n, m);
  155. 	for (int i = 0; i < n; i++)
  156. 		for (tuple<int, int, int> t : b[i])
  157. 		{
  158. 			int to = get<2>(t);
  159. 			int s = get<0>(t);
  160. 			int f = get<1>(t);
  161. 			for (int x = to; x >= i; x--)
  162. 			{
  163. 				if (u[x][s] != -1 && gett(x, s) > f) break;
  164. 				int p = s;
  165. 				while (p <= f)
  166. 				{
  167. 					if (u[x][p] == -1) 
  168. 					{
  169. 						u[x][p] = (i - 1);
  170. 						if (p > 0 && u[x][p - 1] != -1) merge_set(x, p - 1, p);
  171. 						if (p < m - 1 && u[x][p + 1] != -1) merge_set(x, p, p + 1); 
  172. 					}
  173. 					p = gett(x, p);
  174. 				}			
  175. 			}
  176. 		}
  177. 	for (int i = 0; i < n; i++)
  178. 		for (int j = 0; j < m; j++)
  179. 		{
  180. 			if (l[i][j] == -1) l[i][j] = j;
  181. 			if (u[i][j] == -1) u[i][j] = i;
  182. 		}
  183. 	for (int i = 0; i < n; i++)
  184. 		vx[i].init();
  185. 	for (int i = 0; i < m; i++)
  186. 		vy[i].init();      
  187. 	for (int s = 0; s <= (n + m - 2); s++)
  188. 		for (int i = 0; i < min(s + 1, n); i++)
  189. 		{
  190. 			int j = (s - i);
  191. 			if (j < 0 || j >= m) continue;
  192. 			dp[i][j] = 1;
  193. 			kol[i][j] = 1;
  194. 			if (i == 0 || j == 0) continue;
  195. 			vx[i].add(dp[i - 1][j - 1], kol[i - 1][j - 1]);
  196. 			for (int x = l[i][j - 1]; x < l[i][j]; x++)
  197. 				vx[i].del(dp[i - 1][x], kol[i - 1][x]);
  198. 			if (l[i][j] < j)
  199. 			{
  200. 				if (dp[i][j] < vx[i].mx + 1)
  201. 				{
  202. 					dp[i][j] = vx[i].mx + 1;
  203. 					kol[i][j] = 0;
  204. 				}
  205. 				if (dp[i][j] == vx[i].mx + 1)
  206. 				{
  207. 					kol[i][j] += vx[i].sum;
  208. 					if (kol[i][j] >= MOD) kol[i][j] -= MOD;
  209. 				}
  210. 			}
  211. 			vy[j].add(dp[i - 1][j - 1], kol[i - 1][j - 1]);
  212. 			for (int x = u[i - 1][j]; x < u[i][j]; x++)
  213. 				vy[j].del(dp[x][j - 1], kol[x][j - 1]);
  214. 			if (u[i][j] < i)
  215. 			{
  216. 				if (dp[i][j] < vy[j].mx + 1)
  217. 				{
  218. 					dp[i][j] = vy[j].mx + 1;
  219. 					kol[i][j] = 0;
  220. 				}
  221. 				if (dp[i][j] == vy[j].mx + 1)
  222. 				{
  223. 					kol[i][j] += vy[j].sum;
  224. 					if (kol[i][j] >= MOD) kol[i][j] -= MOD;
  225. 				}
  226. 			}
  227. 			if (l[i][j] < j && u[i][j] < i && dp[i][j] == dp[i - 1][j - 1] + 1)
  228. 			{
  229. 				kol[i][j] -= kol[i - 1][j - 1];
  230. 				if (kol[i][j] < 0) kol[i][j] += MOD;
  231. 			}
  232. 		}                               
  233. 	int mx = 0;
  234. 	int ans = 0;
  235. 	for (int i = 0; i < n; i++)
  236. 		for (int j = 0; j < m; j++)
  237.  			mx = max(mx, dp[i][j]);
  238. 	for (int i = 0; i < n; i++)
  239. 		for (int j = 0; j < m; j++)
  240. 			if (mx == dp[i][j])   
  241. 			{
  242. 				ans += kol[i][j];
  243. 				if (ans >= MOD) ans -= MOD;
  244. 			}
  245. 	cout << mx << " " << ans << "\n";					
  246. }
  247.  
  248. int main()
  249. {
  250. 	ios::sync_with_stdio(0);
  251. 	int T;
  252. 	cin >> T;
  253. 	for (int z = 0; z < T; z++)
  254. 		solve();
  255. 	return 0;
  256. }
Success #stdin #stdout 0.01s 8812KB
comments (?)
stdin
copy 
3
3 4 2
1 1 2 2
2 2 3 4
3 3 2
1 1 3 3
1 1 3 3
6 6 2
1 1 4 3
3 2 5 5
stdout
copy 
3 2
3 1
5 1
https://ideone.com/KJfhRg
language:
C++14 (gcc 8.3)
created:
5 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!