| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1353428 | SulA | Lottery (JOI25_lottery) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
int X[n], Y[n];
for (int i = 0; i < n; cin >> X[i++]);
for (int i = 0; i < n; cin >> Y[i++]);
auto check = [&](int l, int r, int k) {
long long mn = 0, mx = 0;
for (int i = l; i < r; i++) {
if (X[i] + Y[i] < k) return false;
mn += max(0, k - Y[i]);
mx += min(X[i], k);
}
long long half = (r-l)/2 * k;
// cout<<l<<' '<<r<<' '<<k<<": "<<mn<<' '<<half<<' '<<mx<<'\n';
return mn <= half && half <= mx;
};
while (q--) {
int l,r; cin >> l >> r; r++;
long long lo = 0, hi = 2e9+1;
while (lo+1 < hi) {
auto mid = (lo + hi)/2;
(check(l, r, mid) ? lo : hi) = mid;
}
cout << lo << "\n";
}
}