fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. void solve() {
  5.     int n , m, q ;
  6.     cin>>n>>m>>q ;
  7.     vector<long long >a(n) , b(m) ;
  8.     for (int i = 0 ; i <n ; i++)
  9.         cin>>a[i];
  10.     for (int i = 0 ; i < m ; i++)
  11.         cin>>b[i];
  12.     sort(a.begin(), a.end()  , greater<int>()) ;
  13.     sort(b.begin(), b.end()  , greater<int>()) ;
  14.     vector<long long >final ;
  15.     int i = 0 , j = 0;
  16.     vector<int>dp1(n+1) ;
  17.     vector<int>dp2 (m+1);
  18.  
  19.     //Creating a final array
  20.     int cnt = 0 ;
  21.     while ( i < n ||  j < m) {
  22.         if (i < n && j <m ) {
  23.             if (a[i]>b[j]) {
  24.                 final.push_back(a[i]);
  25.                 i++;
  26.             }
  27.             else {
  28.                 final.push_back(b[j]);
  29.                 j++;
  30.             }
  31.         }
  32.         else if (i == n ) {
  33.             final.push_back(b[j]);
  34.             j++;
  35.         }
  36.         else {
  37.             final.push_back(a[i]);
  38.             i++;
  39.         }
  40.         // keeping track of last position for a[i] & b[j] element
  41.         dp1[i] = cnt ;
  42.         dp2[j] = cnt ;
  43.         cnt++;
  44.     }
  45.  
  46.     for (int i = 1 ; i <final.size() ; i++) {
  47.         final[i]+= final[i-1];
  48.     }
  49. for(int i = 1 ; i < n ; i++)
  50. a[i]+= a[i-1] ;
  51.  
  52. for(int j = 1 ; j < m ; j++)
  53. b[j]+= b[j-1] ; 
  54.  
  55.  
  56.     vector<long long >ans ;
  57.     for (int i = 0 ; i < q ; i++) {
  58.         int x , y , z ;
  59.         cin>>x>>y>>z  ;
  60.         if (z == 0 )
  61.         {    ans.push_back(0);continue ; }
  62. 	if(x== 0 || y == 0 ) 
  63. 		{
  64. 		if(x == 0 )
  65. {
  66. ans.push_back(b[z-1]);
  67. }
  68. else
  69. {
  70. ans.push_back(a[z-1]);
  71.  
  72. }
  73. continue ; 
  74. }
  75.  
  76.  
  77.         int index1 = dp1[x] +1;
  78.         int index2 = dp2[y]+1;
  79.  
  80.         int index = min(index1 , index2) ;
  81.  
  82. 		if(z <= index )
  83.         {  ans.push_back(final[z-1]); continue ; }
  84.  
  85.         if (index1 == index ) {
  86.            ans.push_back(a[x-1]+ b[z-x - 1 ]);
  87.         }
  88.         else
  89.             ans.push_back(a[z - y-1]+ b[y-1]);
  90.  
  91.     }
  92.     for (int i = 0 ; i < q ; i++)
  93.         cout<<ans[i]<<endl;
  94.  
  95. return ; 
  96. }
  97. int main() {
  98. int t ;
  99. cin>> t ;
  100. while(t--){
  101. solve();
  102. }
  103.  
  104. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1
2 5 2
6 5
12 1 7 9 17
0 0 0
0 5 2
stdout
copy 
0
29
https://ideone.com/2jaWLK
language:
C++ (gcc 8.3)
created:
14 days ago
visibility:
public

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!