71 lines
1.8 KiB
C++
71 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
#define int long long
|
|
|
|
int n,a[200005],b[200005];
|
|
int spa[200005],spb[200005];
|
|
int nxt[200005];
|
|
int rmq[200005][20];
|
|
int lg[200005];
|
|
int v[200005],spv[200005];
|
|
|
|
void calc_nxt()
|
|
{
|
|
///daca astept la poz i, astept la urmatoarea poz pentru care sum(a[j] de la i + 1 la p) > sum(b[j] de la i la p - 1)
|
|
///fie v[j] = a[j] - b[j - 1]
|
|
///de la pozitia i, astept la prima pozitie la care suma(v[j] de la i + 1 la p) > 0
|
|
///din sume partiale pe p, dupa pozitia i mai astept la prima pozitie cu spv[p] > spv[i]
|
|
for (int i = 1; i <= n; i++)
|
|
v[i] = a[i] - b[i - 1];
|
|
for (int i = 1; i <= n; i++)
|
|
spv[i] = spv[i - 1] + v[i];
|
|
spv[n + 1] = 1e18;
|
|
stack<int>s;
|
|
s.push(n + 1);
|
|
for (int i = n; i >= 1; i--)
|
|
{
|
|
while (spv[i] >= spv[s.top()])
|
|
s.pop();
|
|
nxt[i] = s.top();
|
|
s.push(i);
|
|
}
|
|
}
|
|
|
|
signed main()
|
|
{
|
|
ios_base::sync_with_stdio(false);
|
|
cin.tie(NULL);
|
|
cout.tie(NULL);
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++)
|
|
cin >> a[i],spa[i] = a[i] + spa[i - 1];
|
|
for (int i = 1; i <= n; i++)
|
|
cin >> b[i],spb[i] = b[i] + spb[i - 1];
|
|
calc_nxt();
|
|
for (int i = 0; i <= 19; i++)
|
|
rmq[n + 1][i] = n + 1;
|
|
for (int i = 2; i <= n; i++)
|
|
lg[i] = 1 + lg[i / 2];
|
|
for (int i = 1; i <= n; i++)
|
|
rmq[i][0] = nxt[i];
|
|
for (int j = 1; j <= lg[n]; j++)
|
|
for (int i = 1; i <= n; i++)
|
|
rmq[i][j] = rmq[rmq[i][j - 1]][j - 1];
|
|
int q;
|
|
cin >> q;
|
|
for (int i = 1; i <= q; i++)
|
|
{
|
|
int l,r;
|
|
cin >> l >> r;
|
|
int pos = l;
|
|
for (int j = lg[n]; j >= 0; j--)
|
|
if (rmq[pos][j] <= r)
|
|
pos = rmq[pos][j];
|
|
int timp = (spb[r] - spb[pos - 1]) - (spa[r] - spa[pos]);
|
|
cout << timp << '\n';
|
|
}
|
|
return 0;
|
|
}
|