fork download
copy 
  1. #define _USE_MATH_DEFINES
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll long long
  7.  
  8. #define lp(i,n) 	    for(int i=0;i<(int)(n);i++)
  9. #define lpi(i, j, n)    for(int i=(j);i<(int)(n);i++)
  10.  
  11.  
  12. #define all(v)  	 ((v).begin()), ((v).end())
  13.  
  14. #define clr(v, d)    memset(v, d, sizeof(v))
  15.  
  16. #define MP           make_pair
  17.  
  18. ll n,k,t,m,a[1004][1004];
  19.  
  20. ll ans;
  21.  
  22.  
  23.  
  24. int main() {
  25. freopen("dull.in","r",stdin); 
  26.  
  27. ios_base::sync_with_stdio(false);
  28. cin.tie(NULL);  cout.tie(NULL);
  29. cin>>t;
  30. while(t--){
  31. 	clr(a,0);
  32. 	ans=0;
  33. 	cin>>n>>m>>k;
  34. 	if(!k){
  35. 		cout<<"0 "<<n*m<<"\n";
  36. 		continue;
  37. 	}
  38. 	vector<int>x(k),y(k);
  39. 	vector<pair<int,int>>p(k);
  40. 	lp(i,k){
  41. 		cin>>x[i]>>y[i];
  42. 		p[i]=MP(x[i],y[i]);
  43. 	}
  44. 	int cntx=0,cnty=0,curx=0,cury=0;
  45. 	sort(all(x));
  46. 	sort(all(y));
  47. 	map<ll,ll>mpx,mpy,invmpx,invmpy;
  48. 	mpx[0]=x[0]-1;
  49. 	mpy[0]=y[0]-1;
  50. 	lp(i,k){
  51. 		if(curx!=x[i]){
  52. 			mpx[++cntx]=x[i];
  53. 			invmpx[x[i]]=cntx;
  54. 			curx=x[i];
  55. 		}
  56. 		if(cury!=y[i]){
  57. 			mpy[++cnty]=y[i];
  58. 			invmpy[y[i]]=cnty;
  59. 			cury=y[i];
  60. 		}
  61. 	}
  62. 	if(n!=curx)
  63. 		mpx[++cntx]=n;
  64.  
  65. 	if(m!=cury)
  66. 		mpy[++cnty]=m;
  67.  
  68.  
  69. 	lp(i,k)
  70. 		a[invmpx[p[i].first]][invmpy[p[i].second]]=1;
  71.  
  72. 	lp(i,cntx)
  73. 		lp(j,cnty){
  74. 			a[i+1][j+1]+=a[i][j+1];
  75. 			a[i+1][j+1]+=a[i+1][j];
  76. 			a[i+1][j+1]-=a[i][j];
  77. 		}
  78.  
  79. 	lpi(i,1,cntx+1)
  80. 		lpi(j,1,cnty+1){
  81. 			if(a[i][j] & 1 ){
  82. 				ans+=(mpx[i]-mpx[i-1])*(mpy[j]-mpy[j-1]);
  83. 			}
  84.  
  85. 		}
  86.  
  87. 	cout<<ans<<" "<<n*m - ans<<"\n";
  88.  
  89. }
  90.  
  91.  
  92.  
  93. }
  94.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rlIz4D
language:
C++14 (gcc 8.3)
created:
4 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!