#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_], INF = 1e9;
ll IT[SZ+SZ];
struct Node{
int b, e;
vc<pii>D;
}T[SZ+SZ];
int Right(int a){
int x = SZ+a+1;
ll s=0;
while(1){
if(x&1)s+=IT[x];
if(s>w[a])break;
x=(x+1)>>1;
}
while(x<SZ){
x*=2;
s-=IT[x+1];
if(s<=w[a]){
s+=IT[x+1];
x++;
}
}
x-=SZ;x++;
while(s <= w[x]){
s+=w[x];x++;
}
return x;
}
ll Sum(int b, int e){
ll s=0;
b+=SZ,e+=SZ;
while(b<=e){
if(b&1)s+=IT[b];
if(!(e&1))s+=IT[e];
b=(b+1)>>1,e=(e-1)>>1;
}
return s;
}
void Put(int a, ll x){
a+=SZ;
IT[a]=x;
while(a!=1){
a>>=1;
IT[a]=IT[a*2]+IT[a*2+1];
}
}
void UDT(int a, int b){
w[a]=b;
Put(a,b);
}
pii D[N_];
void CalcNode(int nd, int b, int e){
T[nd].b=b,T[nd].e=e;
if(T[nd].D.empty()){
T[nd].D.resize(min(e-b+1,30));
}
gnr(i,e,b){
D[i]={0,i};
if(i!=e && D[i+1].fi) D[i]=D[i+1];
int pv = Right(i);
if(pv<=e && D[i].fi < D[pv].fi + 1 || (D[i].fi == D[pv].fi+1 && D[i].se > D[pv].se))D[i]={D[pv].fi+1, D[pv].se};
}
rng(i,b,min(b+29,e))T[nd].D[i-b]=D[i];
}
pii DD[N_];
Node Merge(Node c1, Node c2){
int b = c1.b, e = c2.e, m = c1.e;
assert(c2.b == m+1);
vi Z;
for(auto &t: c1.D){
Z.pb(t.se);
}
sort(all(Z));
Z.resize(unique(all(Z))-Z.begin());
reverse(all(Z));
int Mx = c2.D[0].fi, ee = c2.D[0].se;
rep(i,si(c2.D)){
DD[m+1+i] = c2.D[i];
}
for(auto &t: Z){
int r = Right(t);
if(r-m-1 < si(c2.D)){
int td = c2.D[r-m-1].fi + 1, te = c2.D[r-m-1].se;
if(Mx<td || (Mx == td && ee > te))Mx=td,ee=te;
}
if(Mx==0 && ee > t)ee = t;
DD[t]={Mx,ee};
}
Mx = c2.D[0].fi, ee = c2.D[0].se;
Node ret;
ret.D.resize(min(30,e-b+1));
per(i,si(ret.D)){
if(i+b>m){
ret.D[i] = DD[i+b];
continue;
}
int x = c1.D[i].se;
int td = DD[x].fi + c1.D[i].fi, te = DD[x].se;
if(Mx < td || (Mx==td && ee>te))Mx=td,ee=te;
ret.D[i] = {Mx,ee};
}
ret.b=b,ret.e=e;
return ret;
}
void init(int nd, int b, int e){
if(b!=e){
int m = (b+e)>>1;
init(nd*2,b,m);
init(nd*2+1,m+1,e);
}
else{
T[nd] = Merge(T[nd*2],T[nd*2+1]);
}
}
vi Z;
void Solve(){
scanf("%d",&n);
rng(i,1,n){
scanf("%d",&w[i]);
UDT(i,w[i]);
}
UDT(n+1,INF+2);
UDT(n+2,INF+1);
rng(i,1,n){
CalcNode(SZ+i,i,i);
}
gnr(i,SZ-1,1){
if(T[i*2].b && T[i*2+1].b){
int b=T[i*2].b, e = T[i*2+1].e;
if(e-b<60) CalcNode(i,b,e);
else T[i] = Merge(T[i*2],T[i*2+1]);
}
}
int Q;
scanf("%d",&Q);
while(Q--){
int x, y, b, e;
scanf("%d%d%d%d",&x,&y,&b,&e);
UDT(x,y);
int a = SZ+x;
while(a!=1){
a>>=1;
if(T[a].b && T[a].e){
if(T[a].e-T[a].b<60)CalcNode(a,T[a].b,T[a].e);
else T[a] = Merge(T[a*2],T[a*2+1]);
}
}
b++;
int tb=b+SZ,te=e+SZ;
vi T1, T2;
while(tb<=te){
if(tb&1)T1.pb(tb);
if(!(te&1))T2.pb(te);
tb=(tb+1)>>1,te=(te-1)>>1;
}
reverse(all(T2));
for(auto &t:T2)T1.pb(t);
Node tp = T[T1[0]];
rng(j,1,si(T1)-1)tp=Merge(tp,T[T1[j]]);
int ans=0;
rep(j,si(tp.D)){
int c = tp.D[j].fi, bb = tp.b+j, ee = tp.D[j].se;
c=c*2+1;
if(Sum(b,b+j-1) > w[bb])c++;
ll ss = Sum(ee+1,e);
rng(k,ee,e-1){
if(ss > w[k]){
c++;
break;
}
ss-=w[k+1];
}
ans=max(ans,c);
}
printf("%d\n",ans);
}
}
int main(){
int TC=1;
while(TC--){
Solve();
}
}
Compilation message
mizuyokan2.cpp: In function 'void CalcNode(int, int, int)':
mizuyokan2.cpp:136:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
136 | if(pv<=e && D[i].fi < D[pv].fi + 1 || (D[i].fi == D[pv].fi+1 && D[i].se > D[pv].se))D[i]={D[pv].fi+1, D[pv].se};
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mizuyokan2.cpp: In function 'void Solve()':
mizuyokan2.cpp:192:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
192 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
mizuyokan2.cpp:194:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | scanf("%d",&w[i]);
| ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:210:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
210 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
mizuyokan2.cpp:213:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
213 | scanf("%d%d%d%d",&x,&y,&b,&e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
9 ms |
25072 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
24924 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
9 ms |
25072 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
24924 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
9 ms |
25072 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
24924 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
24924 KB |
Output is correct |
| 2 |
Incorrect |
685 ms |
46592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
24920 KB |
Output is correct |
| 2 |
Correct |
7 ms |
24924 KB |
Output is correct |
| 3 |
Incorrect |
683 ms |
51932 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
9 ms |
25072 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
24924 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
