#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
ll rand_int(ll l, ll r) { //[l, r]
#ifdef LOCAL
static mt19937_64 gen;
#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif
return uniform_int_distribution<ll>(l, r)(gen);
}
template <uint MD> struct ModInt {
using M = ModInt;
const static M G;
uint v;
ModInt(ll _v = 0) { set_v(_v % MD + MD); }
M& set_v(uint _v) {
v = (_v < MD) ? _v : _v - MD;
return *this;
}
explicit operator bool() const { return v != 0; }
M operator-() const { return M() - *this; }
M operator+(const M& r) const { return M().set_v(v + r.v); }
M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
M operator/(const M& r) const { return *this * r.inv(); }
M& operator+=(const M& r) { return *this = *this + r; }
M& operator-=(const M& r) { return *this = *this - r; }
M& operator*=(const M& r) { return *this = *this * r; }
M& operator/=(const M& r) { return *this = *this / r; }
bool operator==(const M& r) const { return v == r.v; }
M pow(ll n) const {
M x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
M inv() const { return pow(MD - 2); }
friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<998244353>;
using t4 = tuple<int,int,int,int>;
using t5 = tuple<int,int,int,int,int>;
template<> const Mint Mint::G = Mint(3);
#define N_ 251000
const int SZ = (1<<18);
int n, Nxt[N_][20], w[N_];
ll S[N_];
void Solve(){
scanf("%d",&n);
rng(i,1,n){
scanf("%d",&w[i]);
S[i]=S[i-1]+w[i];
}
rng(i,1,n){
int b=i+2,e=n,r=n+1;
while(b<=e){
int mid = (b+e)/2;
if(S[mid-1]-S[i]>w[i]){
r=mid;
e=mid-1;
}
else b=mid+1;
}
while(r<=n && S[r-1]-S[i]<=w[r])r++;
Nxt[i][0]=r;
}
gnr(i,n-1,1)Nxt[i][0]=min(Nxt[i][0],Nxt[i+1][0]);
rep(t,17){
rng(i,1,n){
Nxt[i][t+1]=n+1;
int x = Nxt[i][t];
if(x<=n)Nxt[i][t+1]=Nxt[x][t];
}
}
int Q;
scanf("%d",&Q);
while(Q--){
int x,y,b,e;
scanf("%d%d%d%d",&x,&y,&b,&e);
b++;
int ans=0;
ll Mn = 1e18;
rng(i,b,min(b+30,e)){
int t=i;
int c=1;
per(j,18){
if(Nxt[t][j]<=e){
c+=(1<<j);
t=Nxt[t][j];
}
}
c=c*2-1;
if(S[i-1]-S[b-1] > w[i])c++;
rng(j,t,e){
if(S[e]-S[j] > w[j]){
c++;
break;
}
}
ans=max(ans,c);
}
printf("%d\n",ans);
}
}
int main(){
int TC=1;
while(TC--){
Solve();
}
}
Compilation message
mizuyokan2.cpp: In function 'void Solve()':
mizuyokan2.cpp:112:12: warning: unused variable 'Mn' [-Wunused-variable]
112 | ll Mn = 1e18;
| ^~
mizuyokan2.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
mizuyokan2.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d",&w[i]);
| ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
mizuyokan2.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%d%d%d%d",&x,&y,&b,&e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
95 ms |
19088 KB |
Output is correct |
| 3 |
Correct |
159 ms |
26528 KB |
Output is correct |
| 4 |
Correct |
185 ms |
26452 KB |
Output is correct |
| 5 |
Correct |
153 ms |
26704 KB |
Output is correct |
| 6 |
Correct |
130 ms |
25940 KB |
Output is correct |
| 7 |
Correct |
156 ms |
26116 KB |
Output is correct |
| 8 |
Correct |
138 ms |
25940 KB |
Output is correct |
| 9 |
Correct |
139 ms |
25828 KB |
Output is correct |
| 10 |
Correct |
181 ms |
22308 KB |
Output is correct |
| 11 |
Correct |
245 ms |
27076 KB |
Output is correct |
| 12 |
Correct |
300 ms |
25732 KB |
Output is correct |
| 13 |
Correct |
240 ms |
25664 KB |
Output is correct |
| 14 |
Correct |
213 ms |
25736 KB |
Output is correct |
| 15 |
Correct |
272 ms |
25708 KB |
Output is correct |
| 16 |
Correct |
221 ms |
25620 KB |
Output is correct |
| 17 |
Correct |
110 ms |
26712 KB |
Output is correct |
| 18 |
Correct |
191 ms |
26964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
