Submission #1181179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181179		byunjaewoo	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	100 / 100	1134 ms	435500 KiB

mizuyokan2

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=250010, S=(1<<18);
int n, q, a[N], f[N];

class seg {
public:
    void init() {update(1, n);}
    void update(int l, int r) {update(1, 1, n, l, r);}
    int query(int l, int r) {
        Node tmp=query(1, 1, n, l, r);
        int ret=0;
        for (int i=0; i<tmp.s; i++) {
            ret=max(ret, tmp.g[i][1]-1);
        }
        return 2*ret+1;
    }
private:
    struct Node {
        int p, s;
        array<int, 2> g[51];
        Node operator+(const Node& r) {
            Node ret;
            ret.p=p, ret.s=0;
            for (int i=0; i<s; i++) {
                if (g[i][0]>=r.p+r.s) ret.g[ret.s++]=g[i];
                else ret.g[ret.s++]={r.g[g[i][0]-r.p][0], r.g[g[i][0]-r.p][1]+g[i][1]};
            }
            for (int i=0; i<r.s; i++) {
                if (ret.s>50) break;
                ret.g[ret.s++]=r.g[i];
            }
            return ret;
        }
    }tree[2*S];
    void update(int node, int s, int e, int l, int r) {
        if (s==e) {
            tree[node].p=s, tree[node].s=1, tree[node].g[0][0]=f[s], tree[node].g[0][1]=1;
            return;
        }
        if (s>r || l>e) return;
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        update(lch, s, m, l, r), update(rch, m+1, e, l, r);
        tree[node]=tree[lch]+tree[rch];
    }
    Node query(int node, int s, int e, int l, int r) {
        if (l<=s && e<=r) return tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if (r<=m) return query(lch, s, m, l, r);
        if (l>m) return query(rch, m+1, e, l, r);
        return query(lch, s, m, l, r)+query(rch, m+1, e, l, r);
    }
}T;

class seg2 {
public:
    void init() {
        for (int i=1; i<=n; i++) tree[i+S-1]=a[i];
        for (int i=S-1; i>=1; i--) tree[i]=tree[i<<1]+tree[i<<1|1];
    }
    void update(int k, int v) {
        k+=S-1, tree[k]=v;
        for (k>>=1; k; k>>=1) tree[k]=tree[k<<1]+tree[k<<1|1];
    }
    int query(int l, int r) {
        int ret=0;
        for (l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
            if (l&1) ret+=tree[l++];
            if (!(r&1)) ret+=tree[r--];
        }
        if (l==r) ret+=tree[l];
        return ret;
    }
private:
    int tree[2*S];
}T2;

void init() {
    f[n+1]=n+1;
    for (int i=n; i>=1; i--) {
        f[i]=n+1;
        for (int j=i+2, sum=a[i+1]; j<=min(i+50, n); sum+=a[j++]) if (sum>a[i] && sum>a[j]) {
            f[i]=j; break;
        }
        f[i]=min(f[i], f[i+1]);
    }
    T.init(), T2.init();
}

void update(int k, int v) {
    a[k]=v, T2.update(k, v);
    for (int i=k; i>=max(1ll, k-50); i--) {
        f[i]=n+1;
        for (int j=i+2, sum=a[i+1]; j<=min(n, i+50); sum+=a[j++]) if (sum>a[i] && sum>a[j]) {
            f[i]=j; break;
        }
        f[i]=min(f[i], f[i+1]);
    }
    T.update(max(1ll, k-50), k);
}

int query2(int l, int r) {
    if (r-l+1<3) return -10;
    return T.query(l, r);
}

int query(int l, int r) {
    int ret=1;
    if (T2.query(l, r-1)>a[r]) ret=2;
    if (T2.query(l+1, r)>a[l]) ret=2;
    int ll=r+1, rr=l-1;
    for (int i=l+1, sum=a[l]; i<=r; sum+=a[i++]) if (sum>a[i]) {
        ll=i; break;
    }
    for (int i=r-1, sum=a[r]; i>=l; sum+=a[i--]) if (sum>a[i]) {
        rr=i; break;
    }
    if (ll<=rr) ret=3;
    return max({ret, query2(l, r), query2(ll, r)+1, query2(l, rr)+1, query2(ll, rr)+2});
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    init();
    cin>>q;
    while (q--) {
        int k, v, l, r; cin>>k>>v>>l>>r;
        l++;
        update(k, v), cout<<query(l, r)<<"\n";
    }
    return 0;
}

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