Blog entries - Codeforces

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	141
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	BledDest	132
9	maroonrk	131
10	qwexd	129

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