TUMSO18: Final Crisis

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1e5;

lli qsumA[N + 1], qsumB[N + 1];

int main(){

    int nBio, nHis, Q;
    scanf("%d%d%d", &nBio, &nHis, &Q);
    for(int i = 1; i <= nBio; ++i){
        scanf("%lld", &qsumA[i]);
        qsumA[i] += qsumA[i - 1];
    }
    for(int i = 1; i <= nHis; ++i){
        scanf("%lld", &qsumB[i]);
        qsumB[i] += qsumB[i - 1];
    }

    while(Q--){
        int l1, r1, l2, r2, x;
        scanf("%d%d%d%d%d", &l1, &l2, &r1, &r2, &x);
        int l = max(0, x - r2 + l2 - 1);
        int r = min(x, r1 - l1 + 1);
        lli mn = 1e18;
        while(l <= r){
            int m1 = (l + r) / 2; // Biology
            int m2 = x - m1; // History
            lli biology = qsumA[l1 + m1 - 1] - qsumA[l1 - 1];
            lli history = qsumB[l2 + m2 - 1] - qsumB[l2 - 1];
            mn = min(mn, max(biology, history));
            if(biology == history){
                break;
            } else if(biology > history){
                r = m1 - 1;
            } else {
                l = m1 + 1;
            }
        }
        cout << mn << '\n';
    }

    return 0;
}