Submission #968656

#	Time	Username	Problem	Language	Result	Execution time	Memory
968656		ainta	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	100 / 100	2802 ms	55660 KiB

mizuyokan2

#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];
void UDT(int a, int b){
    w[a]=b;
}
pii D[N_];
int Right[N_];
ll U[110];
int Deq[110]; 
ll S[N_];
void calc(int b, int e){
    S[b-1]=0;
    rng(i,b,e)S[i]=S[i-1]+w[i];
    ll Mn = 1e18;
    int pv = e;
    int head=1,tail=0;
    Right[e]=e+1;
    gnr(i,e-1,b){
        Right[i]=Right[i+1];
        if(Mn > S[i]+w[i]){
            Mn = S[i]+w[i];
        }
        while(S[pv-1] > Mn)pv--;
        rng(j,pv,Right[i]-1){
            if(S[j-1]> S[i]+w[i] && S[j-1]-S[i]>w[j]){
                Right[i]=j;
                break;
            }
        }
    }
}
void CalcNode(int nd, int b, int e){
    T[nd].b=b,T[nd].e=e;
    calc(b,e);
    if(T[nd].D.empty()){
        T[nd].D.resize(min(e-b+1,45));
    }
    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};
    }
    rep(i,si(T[nd].D))T[nd].D[i]=D[i+b];
}
pii DD[N_];
Node Merge(Node c1, Node c2){
    int b = c1.b, e = c2.e, m = c1.e;
    assert(c2.b == m+1);

    int bb = m;

    for(auto &t: c1.D){
        bb=min(bb,t.se);
    }

    calc(bb,min(m+45,e));

    int Mx = c2.D[0].fi, ee = c2.D[0].se;
    rep(i,si(c2.D)){
        DD[m+1+i] = c2.D[i];
    }
    gnr(t,m,max(m-44,b)){
        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(45,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;
        assert(x > m-49);
        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;
        
        ll sss=0;
        calc(max(e-50,1),e);
        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(sss > w[bb])c++;
            sss += w[b+j];
            ll ss = S[e]-S[ee];
            assert(ee>e-50);
            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 (stderr)

mizuyokan2.cpp: In function 'void calc(int, int)':
mizuyokan2.cpp:95:9: warning: unused variable 'head' [-Wunused-variable]
   95 |     int head=1,tail=0;
      |         ^~~~
mizuyokan2.cpp:95:16: warning: unused variable 'tail' [-Wunused-variable]
   95 |     int head=1,tail=0;
      |                ^~~~
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:198:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:201:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         scanf("%d%d%d%d",&x,&y,&b,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 32 / 32
• Subtask 5: 29 / 29
• Subtask 6: 11 / 11