#include <bits/stdc++.h>
using namespace std;
// cartesian tree
/*#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pd_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;
*/
// pragma
/*#pragma GCC optimize("O3")
#pragma GCC target("sse4")
*/
// defines
#define int long long
#define double long double
#define pb push_back
#define FOR(i, a, b) for(int i=a;i<(b);i++)
#define FORD(i, a, b) for(int i=(b)-1;i>=a;i--)
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// consts
const int MOD = 1e9+7;
const int oo = 1e9;
const int OO = 1e18;
const double eps = 1e-9;
const double PI = 4.0 * atan(1.0);
void solve();
signed main() {
fast_io();
solve();
return 0;
}
////////////////////42////////////////////
int n, X[400000], Y[400000];
map<int, int> comprimer, decomprimer;
int cntX[1000*1000],cntY[1000*1000];
void compress(){
set<int> vals;
for(int i=0;i<n;i++)vals.insert(X[i]),vals.insert(Y[i]);
int cnt=0;
for(auto it=vals.begin();it!=vals.end();it++){
comprimer[cnt]=*it;
decomprimer[*it]=cnt;
cnt++;
}
for(int i=0;i<n;i++){
X[i]=comprimer[X[i]];
Y[i]=comprimer[Y[i]];
}
}
void solve() {
cin>>n;
for(int i=0;i<n;i++)cin>>X[i]>>Y[i];
fill_n(cntX, 1000*1000, 0);
fill_n(cntY, 1000*1000, 0);
compress();
set<pair<int, int>> pts;
for(int i=0;i<n;i++){
if(pts.find({X[i],Y[i]})!=pts.end())
continue;
pts.insert({X[i],Y[i]});
cntX[X[i]]++;
cntY[Y[i]]++;
}
int total=0;
for(int i=0;i<n;i++)
total+=max(0LL,(cntX[X[i]]-1LL)*(cntY[Y[i]]-1LL));
cout<<total<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
15992 KB |
Output is correct |
| 2 |
Correct |
12 ms |
16100 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
16100 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
