-
Notifications
You must be signed in to change notification settings - Fork 22
/
triple-sum.cpp
70 lines (47 loc) · 1.31 KB
/
triple-sum.cpp
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define FOR(x, n) for(int x = 0; x < n; x++)
using namespace std;
vector<string> split_string(string);
// Hackerrank triple sum Solution
// Runs in O( n logn ) bounded by sort of longest of a, b c
// ======== SOLUTION =========
long triplets(vector<int> a, vector<int> b, vector<int> c) {
sort(a.begin(), a.end());
sort(b.begin(), b.end());
sort(c.begin(), c.end());
a.erase(unique(a.begin(),a.end()),a.end());
b.erase(unique(b.begin(),b.end()),b.end());
c.erase(unique(c.begin(),c.end()),c.end());
int i = 0, j = 0, k = 0;
long sol = 0;
while(i < b.size()){
while(a[j]<=b[i] && j<a.size())
j++;
while(c[k]<=b[i] && k<c.size())
k++;
sol+= (long)j*k;
i++;
}
return sol;
}
// ======== I/O handling =========
int main()
{
int len_a, len_b, len_c;
long temp;
cin >> len_a;
cin >> len_b;
cin >> len_c;
vector<int> arr_a(len_a);
vector<int> arr_b(len_b);
vector<int> arr_c(len_c);
FOR(i, len_a)
cin >> arr_a[i];
FOR(i, len_b)
cin >> arr_b[i];
FOR(i, len_c)
cin >> arr_c[i];
long sol = triplets(arr_a, arr_b, arr_c);
cout << sol << endl;
return 0;
}