fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long 
  3. #define mp make_pair 
  4. #define f(i,n) for(int i=0;i<n;i++) 
  5. #define F first 
  6. #define S second 
  7. #define pb push_back 
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. using namespace __gnu_pbds; 
  11.  
  12. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
  13.  
  14.  
  15. using namespace std;
  16.  
  17. void test(){
  18. 	ll h,w,m;
  19. 	cin>>h>>w>>m;
  20. 	vector<pair<ll,ll> > row,col;
  21. 	f(i,m){
  22. 		ll a,b;
  23. 		cin>>a>>b;
  24. 		a--,b--;
  25. 		row.pb({a,b});
  26. 		col.pb({b,a});
  27. 	}
  28. 	if(m==0){
  29. 		cout<<h*w<<"\n";
  30. 		return ;
  31. 	}
  32.  
  33. 	sort(row.begin(),row.end());
  34.  
  35. 	ll r_res[h], c_res[w];
  36. 	f(i,h)r_res[i]=w+1;
  37. 	f(i,w)c_res[i]=h+1;
  38. 	f(i,m){
  39. 		r_res[row[i].F] = min(r_res[row[i].F],row[i].S+1);
  40. 		c_res[col[i].F] = min(c_res[col[i].F],col[i].S+1);
  41. 	}
  42.  
  43. 	ll res = 0;
  44. 	f(i,c_res[0]-1){
  45. 		res = res + r_res[i]-1;
  46. 	}
  47. 	f(i,r_res[0]-1){
  48. 		res = res + c_res[i]-1;
  49. 	}
  50.  
  51. 	// remove repeated cases 
  52.  
  53. 	ordered_set st;
  54.  
  55. 	int in = 0;
  56.  
  57. 	f(i,c_res[0]-1){
  58. 		while(in<m and row[in].F==i){
  59. 			st.insert((int)row[in].S);
  60. 			in++;
  61. 		}
  62.  
  63. 		// out of these columns find no's which are less than to r_res[i]-1, r_res[0]-1
  64.  
  65. 		ll rem = st.order_of_key(min(r_res[i]-1,r_res[0]-1));
  66.  
  67. 		res = res - (min(r_res[i]-1,r_res[0]-1)-rem);		
  68. 	}
  69. 	cout<<res<<"\n";
  70. }
  71.  
  72. int main(){
  73. 	std::ios::sync_with_stdio(false);
  74. 	cin.tie(0);
  75. 	cout.tie(0);
  76. 	int tests=1;
  77. //	 cin>>tests;
  78. 	while(tests--){
  79. 		test();
  80. 	}
  81. }
  82.  
Success #stdin #stdout 0s 4796KB
comments (?)
stdin
copy 
5 4 4
3 2
3 4
4 2
5 2
stdout
copy 
14
https://ideone.com/TY5e9B
language:
C++14 (gcc 8.3)
created:
4 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!