This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
int w[N_];
vc<t3> IT[SZ+SZ];
ll BIT[SZ];
void Add(int a, ll b){
while(a<SZ){
BIT[a]+=b;
a+=(a&-a);
}
}
ll Sum(int a){
ll r=0;
while(a){
r += BIT[a];
a-=(a&-a);
}
return r;
}
vc<t3> Merge(vc<t3> A, vc<t3> B){
if(A.empty())return B;
if(B.empty())return A;
vc<t3>T;
for(auto &[c1,b1,e1]: A){
for(auto &[c2,b2,e2]: B){
ll bet = Sum(b2-1)-Sum(e1);
if(w[e1] < bet && bet > w[b2]){
T.pb({c1+c2,b1,e2});
}
}
}
for(auto &t: A)T.pb(t);
for(auto &t: B)T.pb(t);
sort(all(T), [&](t3 a, t3 b){
auto [c1,b1,e1]=a;
auto [c2,b2,e2]=b;
if(c1!=c2)return c1<c2;
return e1-b1 > e2-b2;
});
reverse(all(T));
vc<t3>ret;
rep(i,si(T)){
int ck=0;
auto [c,b,e]=T[i];
rep(j,si(ret)){
auto [c2,b2,e2]=ret[j];
if(c+2<c2){
ck=1;
break;
}
if(c+1<c2 && j>10){
ck=1;
break;
}
if(b2>=b && e2<=e){
if(b2-b >30 || ((ll)w[b] << (b2-b)) >= w[b2]){
if(e-e2 > 30 || ((ll)w[e] << (e-e2)) >= w[e2] ){
ck=1;
break;
}
}
}
}
if(!ck)ret.pb(T[i]);
}
//printf("! %d\n",si(ret));
return ret;
}
vc<t3> Leaf(int a){
return {{1,a,a}};
}
void Get(int l, int r){
vi T1, T2;
int b=l+SZ,e=r+SZ;
while(b<=e){
if(b&1)T1.pb(b);
if(!(e&1))T2.pb(e);
b=(b+1)>>1,e=(e-1)>>1;
}
reverse(all(T2));
for(auto &t:T2)T1.pb(t);
auto ret = IT[T1[0]];
rng(i,1,si(T1)-1){
ret = Merge(ret, IT[T1[i]]);
}
ll SB = Sum(l-1);
ll SE = Sum(r);
int Mx=0;
for(auto &[c1,b1,e1]: ret){
int c=c1*2-1;
if(Sum(b1-1)-SB > w[b1]) c++;
if(SE-Sum(e1) > w[e1]) c++;
Mx=max(Mx,c);
}
printf("%d\n",Mx);
}
void UDT(int i){
int a = SZ+i;
IT[a] = Leaf(i);
while(a!=1){
a>>=1;
IT[a] = Merge(IT[a*2],IT[a*2+1]);
}
}
void Solve(){
scanf("%d",&n);
rng(i,1,n){
scanf("%d",&w[i]);
Add(i,w[i]);
}
rng(i,1,n){
UDT(i);
}
int Q;
scanf("%d",&Q);
while(Q--){
int x, y, b, e;
scanf("%d%d%d%d",&x,&y,&b,&e);
Add(x,y-w[x]);
w[x]=y;
UDT(x);
b++;
Get(b,e);
}
}
int main(){
int TC=1;
while(TC--){
Solve();
}
}
Compilation message (stderr)
mizuyokan2.cpp: In function 'void Solve()':
mizuyokan2.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
mizuyokan2.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
182 | scanf("%d",&w[i]);
| ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:189:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
189 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
mizuyokan2.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
192 | scanf("%d%d%d%d",&x,&y,&b,&e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |