codeforces #345 div 2 C. Watchmen (容斥)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年03月07日 星期一 18时43分02秒
  4File Name :code/C.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=2E6+7;
 34
 35struct node
 36{
 37    int x,y;
 38
 39    bool operator < (node b)const
 40    {
 41	if (x==b.x) return y<b.y;
 42	return x<b.x;
 43    }
 44}p[N];
 45
 46
 47
 48bool cmp( node a,node b)
 49{
 50    return a.y<b.y;
 51}
 52LL cal( LL x)
 53{
 54    LL res = x*(x+1)/2;
 55    return res;
 56}
 57int n;
 58LL a,b,c;
 59LL cnta,cntb,cntc;
 60int main()
 61{
 62	#ifndef  ONLINE_JUDGE 
 63	freopen("code/in.txt","r",stdin);
 64  #endif
 65
 66	ios::sync_with_stdio(false);
 67	cin>>n;
 68	for ( int i = 1 ;i  <= n ; i++) cin>>p[i].x>>p[i].y;
 69
 70	sort(p+1,p+n+1);
 71
 72	a=b=c=0LL;
 73	cnta=cntb=cntc=0LL;
 74
 75
 76	for ( int i = 1 ; i <= n-1 ; i++)
 77	{
 78	    if (p[i].x==p[i+1].x)
 79	    {
 80		cnta++;
 81	    }
 82	    else
 83	    {
 84		a+=cal(cnta);
 85		cnta = 0 ;
 86	    }
 87	}
 88	a +=cal(cnta);
 89
 90
 91	for ( int i = 1 ; i <= n-1 ; i++)
 92	{
 93	    if (p[i].x==p[i+1].x&&p[i].y==p[i+1].y)
 94	    {
 95		cntc++;
 96	    }
 97	    else
 98	    {
 99		c +=cal(cntc);
100		cntc = 0 ;
101	    }
102	}
103
104	c+=cal(cntc);
105
106
107
108	sort(p+1,p+n+1,cmp);
109	for ( int i =  1 ; i  <= n-1 ; i ++)
110	{
111	    if (p[i].y==p[i+1].y)
112	    {
113		cntb++;
114	    }
115	    else
116	    {
117		b +=cal(cntb);
118		cntb = 0 ;
119	    }
120	}
121	b +=cal(cntb);
122
123	LL ans=0LL;
124	ans = a+b-c;
125	cout<<ans<<endl;
126
127  #ifndef ONLINE_JUDGE  
128  fclose(stdin);
129  #endif
130    return 0;
131}