fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <assert.h>
  5. using namespace std;
  6.  
  7.  
  8.  
  9. long long readInt(long long l,long long r,char endd){
  10. 	long long x=0;
  11. 	int cnt=0;
  12. 	int fi=-1;
  13. 	bool is_neg=false;
  14. 	while(true){
  15. 		char g=getchar();
  16. 		if(g=='-'){
  17. 			assert(fi==-1);
  18. 			is_neg=true;
  19. 			continue;
  20. 		}
  21. 		if('0'<=g && g<='9'){
  22. 			x*=10;
  23. 			x+=g-'0';
  24. 			if(cnt==0){
  25. 				fi=g-'0';
  26. 			}
  27. 			cnt++;
  28. 			assert(fi!=0 || cnt==1);
  29. 			assert(fi!=0 || is_neg==false);
  30.  
  31. 			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
  32. 		} else if(g==endd){
  33. 			assert(cnt>0);
  34. 			if(is_neg){
  35. 				x= -x;
  36. 			}
  37. 			assert(l<=x && x<=r);
  38. 			return x;
  39. 		} else {
  40. 			assert(false);
  41. 		}
  42. 	}
  43. }
  44. string readString(int l,int r,char endd){
  45. 	string ret="";
  46. 	int cnt=0;
  47. 	while(true){
  48. 		char g=getchar();
  49. 		assert(g!=-1);
  50. 		if(g==endd){
  51. 			break;
  52. 		}
  53. 		cnt++;
  54. 		ret+=g;
  55. 	}
  56. 	assert(l<=cnt && cnt<=r);
  57. 	return ret;
  58. }
  59. long long readIntSp(long long l,long long r){
  60. 	return readInt(l,r,' ');
  61. }
  62. long long readIntLn(long long l,long long r){
  63. 	return readInt(l,r,'\n');
  64. }
  65. string readStringLn(int l,int r){
  66. 	return readString(l,r,'\n');
  67. }
  68. string readStringSp(int l,int r){
  69. 	return readString(l,r,' ');
  70. }
  71. struct rect{
  72. 	int r1,r2;
  73. 	int c1,c2;
  74. };
  75. bool comp(rect a,rect b){
  76. 	return a.r1 < b.r1;
  77. }
  78. bool comp2(rect a,rect b){
  79. 	return a.c1 < b.c1;
  80. }
  81. int T;
  82. int n,m,q;
  83. int sgt[40400];
  84. int idx[40400];
  85. rect arr[500500];
  86. int sm_nm=0,sm_q=0;
  87.  
  88. void build(int nd,int l,int r){
  89. 	if(l==r){
  90. 		sgt[nd] = -1;
  91. 		idx[nd]= l;
  92. 		return;
  93. 	}
  94. 	int m=(r+l)/2;
  95. 	build(2*nd,l,m);
  96. 	build(2*nd+1,m+1,r);
  97. 	if(sgt[2*nd]< sgt[2*nd+1]){
  98. 		sgt[nd] = sgt[2*nd];
  99. 		idx[nd] = idx[2*nd];
  100. 	} else {
  101. 		sgt[nd] = sgt[2*nd+1];
  102. 		idx[nd] = idx[2*nd+1];
  103. 	}
  104. }
  105.  
  106. void update(int nd,int l,int r,int ind,int val){
  107. 	if(l==r){
  108. 		sgt[nd] = val;
  109. 		return;
  110. 	}
  111. 	int m=(r+l)/2;
  112. 	if(ind <= m){
  113. 		update(2*nd,l,m,ind,val);
  114. 	} else {
  115. 		update(2*nd+1,m+1,r,ind,val);
  116. 	}
  117. 	if(sgt[2*nd]< sgt[2*nd+1]){
  118. 		sgt[nd] = sgt[2*nd];
  119. 		idx[nd] = idx[2*nd];
  120. 	} else {
  121. 		sgt[nd] = sgt[2*nd+1];
  122. 		idx[nd] = idx[2*nd+1];
  123. 	}
  124. }
  125.  
  126.  
  127.  
  128. pair<int,int> query(int nd,int l,int r,int s, int e){
  129. 	if(s<=l && r<=e){
  130. 		return make_pair(sgt[nd],idx[nd]);
  131. 	}
  132. 	int m=(r+l)/2;
  133. 	pair<int,int> ret = make_pair(100000,-1);
  134. 	if(s<=m){
  135. 		ret = query(2*nd,l,m,s,e);
  136. 	}
  137. 	if(m+1<=e){
  138. 		pair<int,int> g = query(2*nd+1,m+1,r,s,e);
  139. 		if(ret.first > g.first){
  140. 			ret = g;
  141. 		}
  142. 	}
  143. 	return ret;
  144. }
  145.  
  146. int down[2020][2020];
  147. int lft[2020][2020];
  148.  
  149. // remember the case when there's only one rectangle 1 1 1 4
  150.  
  151. int dp[2020][2020];
  152. int cnt[2020][2020];
  153.  
  154. int mod=1000000007;
  155. int main(){
  156. 	T=readIntLn(1,1000);
  157. 	while(T--){
  158. 		n=readIntSp(1,2000);
  159. 		m=readIntSp(1,2000);
  160. 		q=readIntLn(1,500000);
  161. 		sm_nm += n*m;
  162. 		assert(sm_nm<=10000000);
  163. 		sm_q += q;
  164. 		assert(sm_q<=500000);
  165. 		for(int i=0;i<q;i++){
  166. 			arr[i].r1 = readIntSp(1,n);
  167. 			arr[i].c1 = readIntSp(1,m);
  168. 			arr[i].r2 = readIntSp(1,n);
  169. 			arr[i].c2 = readIntLn(1,m);
  170. 		}
  171. 		for(int i=1;i<=n;i++){
  172. 			for(int j=1;j<=m;j++){
  173. 				down[i][j] = lft[i][j] = -1;
  174. 			}
  175. 		}
  176. 		sort(arr,arr+q,comp);
  177. 		build(1,1,m);
  178. 		for(int i=0;i<q;i++){
  179. 			if(arr[i].c1 == arr[i].c2 || arr[i].r1 == arr[i].r2)continue;
  180. 			pair<int,int> h = query(1,1,m,arr[i].c1+1,arr[i].c2);
  181. 			while(h.first <= arr[i].r2){
  182. 				for(int j = max(h.first,arr[i].r1+1);j<=arr[i].r2;j++){
  183. 					down[j][h.second] = arr[i].r1;
  184. 				}
  185. 				update(1,1,m,h.second,arr[i].r2+1);
  186. 				h = query(1,1,m,arr[i].c1+1,arr[i].c2);
  187. 			}
  188. 		}
  189. 		/*for(int i=1;i<=n;i++){
  190. 			for(int j=1;j<=m;j++){
  191. 				cout<<down[i][j]<<" ";
  192. 			}
  193. 			cout<<endl;
  194. 		}
  195. 		while(1);*/
  196. 		sort(arr,arr+q,comp2);
  197. 		build(1,1,n);
  198. 		for(int i=0;i<q;i++){
  199. 			if(arr[i].c1 == arr[i].c2 || arr[i].r1 == arr[i].r2)continue;
  200. 			pair<int,int> h = query(1,1,n,arr[i].r1+1,arr[i].r2);
  201. 			while(h.first <= arr[i].c2){
  202. 				for(int j = max(h.first,arr[i].c1+1);j<=arr[i].c2;j++){
  203. 					lft[h.second][j] = arr[i].c1;
  204. 				}
  205. 				update(1,1,n,h.second,arr[i].c2+1);
  206. 				h = query(1,1,n,arr[i].r1+1,arr[i].r2);
  207. 			}
  208. 		}
  209. 		int sol = 0;
  210. 		int co = 0;
  211. 		for(int i=1;i<=n;i++){
  212. 			for(int j=1;j<=m;j++){
  213. 				dp[i][j] = 1;
  214. 				cnt[i][j] = 1;
  215. 				if ( down[i][j] != -1)
  216. 				for(int k=down[i][j] ; k<=i-2;k++){
  217. 					if(dp[k][j-1] + 1 > dp[i][j] ){
  218. 						dp[i][j] = dp[k][j-1] + 1;
  219. 						cnt[i][j] = cnt[k][j-1];
  220. 					} else if(dp[k][j-1] + 1 == dp[i][j] ){
  221. 						cnt[i][j] += cnt[k][j-1];
  222. 						cnt[i][j] %= mod;
  223. 					}
  224. 				}
  225. 				if ( lft[i][j] != -1)
  226. 				for(int k=lft[i][j] ; k<=j-1;k++){
  227. 					if(dp[i-1][k] + 1 > dp[i][j] ){
  228. 						dp[i][j] = dp[i-1][k] + 1;
  229. 						cnt[i][j] = cnt[i-1][k];
  230. 					} else if(dp[i-1][k] + 1 == dp[i][j] ){
  231. 						cnt[i][j] += cnt[i-1][k];
  232. 						cnt[i][j] %= mod;
  233. 					}
  234. 				}
  235. 				if(dp[i][j]  > sol ){
  236. 					sol = dp[i][j];
  237. 					co = cnt[i][j];
  238. 				} else if (dp[i][j]  == sol){
  239. 					co += cnt[i][j];
  240. 					co %= mod;
  241. 				}
  242. 			}
  243. 		}
  244. 		cout<<sol<<" "<<co<<endl;
  245. 	}
  246. 	assert(getchar()==-1);
  247. }
Success #stdin #stdout 0s 4380KB
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/GrQqjk
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!