1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
const int maxn = 1000;
int a[maxn+5];
int n;
// we have first < second
map<int, vector<pair<int,int> > > position;
long long compute(vector<pair<int, int> > pairs) {
    // sort by the first element, into different groups
    // then the answer is just the multiplication of different group size - invalid pairs
    // the number of invalid pairs is the one with the same second element
    map<pair<int, int>, int> y2count; // map[y][group]
    map<pair<int, int>, int> x2count; // map[x][group]
    vector<int> last; // index of last element of group i
    
    int group = 0;
    for (int i = 0; i < pairs.size(); ++i) {
        if (i > 0 && pairs[i].first != pairs[i-1].first) {
            group++;
            last.push_back(i);
        }
        x2count[{pairs[i].first, group}] ++;
        y2count[{pairs[i].second, group}] ++;
    }
    last.push_back(pairs.size());
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX