Blog entries - Codeforces

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

#	User	Contrib.
1	Qingyu	156
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	135
9	maroonrk	132
10	cry	130

Problem.

I solved the problem with three pointers. But when I sort the vectors first and the resize, I get an AC. If I sort them after making them unique, I get a WA.

AC Code

long triplets(vector<int> a, vector<int> b, vector<int> c) {
    sort(all(a));
    sort(all(b));
    sort(all(c));
    a.erase(unique(all(a)), a.end());
    b.erase(unique(all(b)), b.end());
    c.erase(unique(all(c)), c.end());
    int n = a.size(), m = b.size(), l = c.size();
    int i = 0, j = 0, k = 0;
    long ans = 0;
    for(int j = 0; j < m; j++) {
        while(i < n and a[i] <= b[j]) i++;
        while(k < l and c[k] <= b[j]) k++;
        ans += 1LL*i*k;
    }
    return ans;
}

WA Code

long triplets(vector<int> a, vector<int> b, vector<int> c) {
    a.erase(unique(all(a)), a.end());
    b.erase(unique(all(b)), b.end());
    c.erase(unique(all(c)), c.end());
    sort(all(a));
    sort(all(b));
    sort(all(c));
    int n = a.size(), m = b.size(), l = c.size();
    int i = 0, j = 0, k = 0;
    long ans = 0;
    for(int j = 0; j < m; j++) {
        while(i < n and a[i] <= b[j]) i++;
        while(k < l and c[k] <= b[j]) k++;
        ans += 1LL*i*k;
    }
    return ans;
}

Full text and comments »

aneee's blog