Blog entries - Codeforces

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

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