AlaminSakib

Triple Sum [Hacker Rank, Searching]

Jan 1st, 2020
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<string> split_string(string);
  6.  
  7. // Complete the triplets function below.
  8. long triplets(vector<int> a, vector<int> b, vector<int> c) {
  9.     sort(b.begin(), b.end());
  10.     sort(c.begin(), c.end());
  11.     long cnt = 0;
  12.     for(int i = 0; i < b.size(); i++)
  13.     {
  14.         int left = 0, right = a.size() - 1, key = b[i], aee = 0, cee = 0, mid;
  15.         while(left < right)
  16.         {
  17.             int mid = left + (right - left) / 2;
  18.             if(key == a[mid])
  19.             {
  20.                 while(mid < a.size() - 1)
  21.                 {
  22.                     if(a[mid + 1] == key) mid++;
  23.                 }
  24.             }
  25.             else if(key < a[mid]) right = mid;
  26.             else left = mid + 1;
  27.         }
  28.         while (mid > -1 && a[mid] > key)
  29.         {
  30.             mid--;
  31.         }
  32.         aee = mid + 1;
  33.         left = 0; right = c.size() - 1;
  34.         while(left < right)
  35.         {
  36.             int mid = left + (right - left) / 2;
  37.             if(key == c[mid])
  38.             {
  39.                 while(mid < c.size() - 1)
  40.                 {
  41.                     if(c[mid + 1] == key) mid++;
  42.                 }
  43.             }
  44.             else if(key < c[mid]) right = mid;
  45.             else left = mid + 1;
  46.         }
  47.         while (mid > -1 && c[mid] > key)
  48.         {
  49.             mid--;
  50.         }
  51.         cee = mid + 1;
  52.         cnt += aee * cee;
  53.     }
  54.     return cnt;
  55. }
  56.  
  57. int main()
  58. {
  59.     ofstream fout(getenv("OUTPUT_PATH"));
  60.  
  61.     string lenaLenbLenc_temp;
  62.     getline(cin, lenaLenbLenc_temp);
  63.  
  64.     vector<string> lenaLenbLenc = split_string(lenaLenbLenc_temp);
  65.  
  66.     int lena = stoi(lenaLenbLenc[0]);
  67.  
  68.     int lenb = stoi(lenaLenbLenc[1]);
  69.  
  70.     int lenc = stoi(lenaLenbLenc[2]);
  71.  
  72.     string arra_temp_temp;
  73.     getline(cin, arra_temp_temp);
  74.  
  75.     vector<string> arra_temp = split_string(arra_temp_temp);
  76.  
  77.     vector<int> arra(lena);
  78.  
  79.     for (int i = 0; i < lena; i++) {
  80.         int arra_item = stoi(arra_temp[i]);
  81.  
  82.         arra[i] = arra_item;
  83.     }
  84.  
  85.     string arrb_temp_temp;
  86.     getline(cin, arrb_temp_temp);
  87.  
  88.     vector<string> arrb_temp = split_string(arrb_temp_temp);
  89.  
  90.     vector<int> arrb(lenb);
  91.  
  92.     for (int i = 0; i < lenb; i++) {
  93.         int arrb_item = stoi(arrb_temp[i]);
  94.  
  95.         arrb[i] = arrb_item;
  96.     }
  97.  
  98.     string arrc_temp_temp;
  99.     getline(cin, arrc_temp_temp);
  100.  
  101.     vector<string> arrc_temp = split_string(arrc_temp_temp);
  102.  
  103.     vector<int> arrc(lenc);
  104.  
  105.     for (int i = 0; i < lenc; i++) {
  106.         int arrc_item = stoi(arrc_temp[i]);
  107.  
  108.         arrc[i] = arrc_item;
  109.     }
  110.  
  111.     long ans = triplets(arra, arrb, arrc);
  112.  
  113.     fout << ans << "\n";
  114.  
  115.     fout.close();
  116.  
  117.     return 0;
  118. }
  119.  
  120. vector<string> split_string(string input_string) {
  121.     string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
  122.         return x == y and x == ' ';
  123.     });
  124.  
  125.     input_string.erase(new_end, input_string.end());
  126.  
  127.     while (input_string[input_string.length() - 1] == ' ') {
  128.         input_string.pop_back();
  129.     }
  130.  
  131.     vector<string> splits;
  132.     char delimiter = ' ';
  133.  
  134.     size_t i = 0;
  135.     size_t pos = input_string.find(delimiter);
  136.  
  137.     while (pos != string::npos) {
  138.         splits.push_back(input_string.substr(i, pos - i));
  139.  
  140.         i = pos + 1;
  141.         pos = input_string.find(delimiter, i);
  142.     }
  143.  
  144.     splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
  145.  
  146.     return splits;
  147. }
Add Comment
Please, Sign In to add comment