fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. template<class T> long long counterProdIsLT(int As, T A[], int Bs, T B[], T val){
  7.   int i;
  8.   int j;
  9.   int ma = 0;
  10.   int za = 0;
  11.   int pa = 0;
  12.   int mb = 0;
  13.   int zb = 0;
  14.   int pb = 0;
  15.   long long res = 0;
  16.   i = 0;
  17.   while(i < As && A[i] < 0){
  18.     i++;
  19.   }
  20.   ma = i;
  21.   while(i < As && A[i] == 0){
  22.     i++;
  23.   }
  24.   za = i - ma;
  25.   pa = As - i;
  26.   i = 0;
  27.   while(i < Bs && B[i] < 0){
  28.     i++;
  29.   }
  30.   mb = i;
  31.   while(i < Bs && B[i] == 0){
  32.     i++;
  33.   }
  34.   zb = i - mb;
  35.   pb = Bs - i;
  36.   if(val < 0){
  37.     j = 0;
  38.     for(i=(0);i<(pa);i++){
  39.       while(j < mb && A[As-pa+i] * B[j] < val){
  40.         j++;
  41.       }
  42.       res += j;
  43.     }
  44.     j = 0;
  45.     for(i=(0);i<(pb);i++){
  46.       while(j < ma && B[Bs-pb+i] * A[j] < val){
  47.         j++;
  48.       }
  49.       res += j;
  50.     }
  51.   }
  52.   else if(val == 0){
  53.     res = (long long) ma * pb + (long long) pa * mb;
  54.   }
  55.   else{
  56.     res = (long long) As * Bs - (long long) pa * pb - (long long) ma * mb;
  57.     j = pb;
  58.     for(i=(0);i<(pa);i++){
  59.       while(j && A[As-pa+i] * B[Bs-pb+j-1] >= val){
  60.         j--;
  61.       }
  62.       if(j==0){
  63.         break;
  64.       }
  65.       res += j;
  66.     }
  67.     j = mb;
  68.     for(i=(0);i<(ma);i++){
  69.       while(j && A[ma-1-i] * B[mb-j] >= val){
  70.         j--;
  71.       }
  72.       if(j==0){
  73.         break;
  74.       }
  75.       res += j;
  76.     }
  77.   }
  78.   return res;
  79. }
  80. template<class T, class S> inline int vec2arr(vector<T> &v, S arr[]){
  81.   int i;
  82.   int N = v.size();
  83.   for(i=(0);i<(N);i++){
  84.     arr[i] = v[i];
  85.   }
  86.   return N;
  87. }
  88. template<class T, class S1, class S2> inline int vec2arr(vector<vector<T>> &v, S1 arr1[], S2 arr2[]){
  89.   int i;
  90.   int N = v.size();
  91.   for(i=(0);i<(N);i++){
  92.     arr1[i] = v[i][0];
  93.     arr2[i] = v[i][1];
  94.   }
  95.   return N;
  96. }
  97. template<class T, class S1, class S2, class S3> inline int vec2arr(vector<vector<T>> &v, S1 arr1[], S2 arr2[], S3 arr3[]){
  98.   int i;
  99.   int N = v.size();
  100.   for(i=(0);i<(N);i++){
  101.     arr1[i] = v[i][0];
  102.     arr2[i] = v[i][1];
  103.     arr3[i] = v[i][2];
  104.   }
  105.   return N;
  106. }
  107. #define main dummy_main
  108. int main(){
  109.   return 0;
  110. }
  111. #undef main
  112. int As;
  113. int Bs;
  114. long long A[100000];
  115. long long B[100000];
  116. class Solution{
  117.   public:
  118.   long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long K){
  119.     dummy_main();
  120.     As = vec2arr(nums1, A);
  121.     Bs = vec2arr(nums2, B);
  122.     long long Lj4PdHRW;
  123.     long long KL2GvlyY;
  124.     long long Q5VJL1cS;
  125.     Lj4PdHRW = -10000000000LL;
  126.     KL2GvlyY = 10000000000LL;
  127.     while(Lj4PdHRW < KL2GvlyY){
  128.       if((Lj4PdHRW + KL2GvlyY)%2==0){
  129.         Q5VJL1cS = (Lj4PdHRW + KL2GvlyY) / 2;
  130.       }
  131.       else{
  132.         Q5VJL1cS = (Lj4PdHRW + KL2GvlyY + 1) / 2;
  133.       }
  134.       if(counterProdIsLT(As, A, Bs, B, Q5VJL1cS) < K){
  135.         Lj4PdHRW = Q5VJL1cS;
  136.       }
  137.       else{
  138.         KL2GvlyY = Q5VJL1cS - 1;
  139.       }
  140.     }
  141.     return KL2GvlyY;
  142.   }
  143. }
  144. ;
  145. // cLay version 20210926-1
  146.  
  147. // --- original code ---
  148. // #define main dummy_main
  149. // {}
  150. // #undef main
  151. // 
  152. // int As, Bs; ll A[1d5], B[];
  153. // 
  154. // class Solution {
  155. // public:
  156. //   ll kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, ll K) {
  157. //     dummy_main();
  158. //     As = vec2arr(nums1, A);
  159. //     Bs = vec2arr(nums2, B);
  160. //     return bsearch_max[ll,x,-1d10,1d10](counterProdIsLT(As, A, Bs, B, x) < K);
  161. //   }
  162. // };
  163.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/qzW9Gq
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!