mickypinata

TUMSO18: Final Crisis

Jul 24th, 2021
1,225
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int N = 1e5;
  7.  
  8. lli qsumA[N + 1], qsumB[N + 1];
  9.  
  10. int main(){
  11.  
  12.     int nBio, nHis, Q;
  13.     scanf("%d%d%d", &nBio, &nHis, &Q);
  14.     for(int i = 1; i <= nBio; ++i){
  15.         scanf("%lld", &qsumA[i]);
  16.         qsumA[i] += qsumA[i - 1];
  17.     }
  18.     for(int i = 1; i <= nHis; ++i){
  19.         scanf("%lld", &qsumB[i]);
  20.         qsumB[i] += qsumB[i - 1];
  21.     }
  22.  
  23.     while(Q--){
  24.         int l1, r1, l2, r2, x;
  25.         scanf("%d%d%d%d%d", &l1, &l2, &r1, &r2, &x);
  26.         int l = max(0, x - r2 + l2 - 1);
  27.         int r = min(x, r1 - l1 + 1);
  28.         lli mn = 1e18;
  29.         while(l <= r){
  30.             int m1 = (l + r) / 2; // Biology
  31.             int m2 = x - m1; // History
  32.             lli biology = qsumA[l1 + m1 - 1] - qsumA[l1 - 1];
  33.             lli history = qsumB[l2 + m2 - 1] - qsumB[l2 - 1];
  34.             mn = min(mn, max(biology, history));
  35.             if(biology == history){
  36.                 break;
  37.             } else if(biology > history){
  38.                 r = m1 - 1;
  39.             } else {
  40.                 l = m1 + 1;
  41.             }
  42.         }
  43.         cout << mn << '\n';
  44.     }
  45.  
  46.     return 0;
  47. }
  48.  
RAW Paste Data