Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
6	adamant	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

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