제출 #1188435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188435		12345678	Fish 2 (JOI22_fish2)	C++17	8 / 100	201 ms	18852 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll n, a[nx], q, t, l, r, ql, qr;

struct segtreesum
{
    ll d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=a[l], void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
    }
    void update(int l, int r, int i, int idx, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md ,2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql||qr<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md ,2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} sm;

struct segtreeleft
{
    // qs[i]-qs[l-1] < a[i+1] -> qs[i]-a[i+1] < qs[l-1]
    ll d[4*nx], lz[4*nx];
    void apply(int l, int r, int i, ll vl)
    {
        d[i]+=vl;
        lz[i]+=vl;
    }
    void pushlz(int l, int r, int i)
    {
        apply(l, r, i, lz[i]);
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=sm.query(1, n, 1, 1, l)-a[l+1], void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return apply(l, r, i, vl);
        int md=(l+r)/2;
        pushlz(l, r, i);
        update(l, md, 2*i, ql, qr ,vl);
        update(l, md, 2*i, ql, qr, vl);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    ll query(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<l||r<ql||d[i]>=vl) return ql-1;
        if (l==r) return l;
        int md=(l+r)/2;
        pushlz(l, r, i);
        auto tmp=query(md+1, r, 2*i+1, ql, qr, vl);
        if (tmp<ql) return query(l, md, 2*i, ql, qr, vl);
        return tmp;
    }
    void queryfill(int l, int r, int i, int ql, int qr, ll vl, vector<int> &v)
    {
        if (qr<l||r<ql||d[i]>=vl) return;
        if (l==r) return v.push_back(l), void();
        int md=(l+r)/2;
        pushlz(l, r, i);
        queryfill(l, md, 2*i, ql, qr, vl, v);
        queryfill(md+1, r, 2*i+1, ql, qr ,vl, v);
    }
} ls;

struct segtreeright
{
    // qs[r] - qs[i-1] < a[i-1] -> qs[r] < a[i-1] + qs[i-1]
    ll d[4*nx], lz[4*nx];
    void apply(int l, int r, int i, ll vl)
    {
        d[i]+=vl;
        lz[i]+=vl;
    }
    void pushlz(int l, int r, int i)
    {
        apply(l, r, i, lz[i]);
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=sm.query(1, n, 1, 1, l-1)+a[l-1], void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return apply(l, r, i, vl);
        int md=(l+r)/2;
        pushlz(l, r, i);
        update(l, md, 2*i, ql, qr ,vl);
        update(l, md, 2*i, ql, qr, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    ll query(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<l||r<ql||d[i]<=vl) return qr+1;
        if (l==r) return l;
        int md=(l+r)/2;
        pushlz(l, r, i);
        auto tmp=query(l, md, 2*i, ql, qr, vl);
        if (tmp>qr) return query(md+1, r, 2*i+1, ql, qr, vl);
        return tmp;
    }
    void queryfill(int l, int r, int i, int ql, int qr, ll vl, vector<int> &v)
    {
        if (qr<l||r<ql||d[i]<=vl) return;
        //if (l==r) cout<<"debug "<<l<<' '<<d[i]<<' '<<vl<<'\n';
        if (l==r) return v.push_back(l), void();
        int md=(l+r)/2;
        pushlz(l, r, i);
        queryfill(l, md, 2*i, ql, qr, vl, v);
        queryfill(md+1, r, 2*i+1, ql, qr ,vl, v);
    }
} rs;

struct segtreefreq
{
    struct node
    {
        ll mn, f, lz;
        node(): mn(1e18), f(0), lz(0){}
    } d[4*nx];
    void apply(int i, ll vl)
    {
        d[i].mn+=vl;
        d[i].lz+=vl;
    }
    void pushlz(int i)
    {
        apply(2*i, d[i].lz);
        apply(2*i+1, d[i].lz);
        d[i].lz=0;
    }
    node merge(node l, node r)
    {
        node res;
        res.mn=min(l.mn, r.mn);
        res.f=(l.f*(l.mn==res.mn))+(r.f*(r.mn==res.mn));
        return res;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i].mn=0, d[i].f=1, d[i].lz=0, void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return apply(i, vl);
        int md=(l+r)/2;
        pushlz(i);
        update(l, md, 2*i, ql, qr ,vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void show(int l, int r, int i)
    {
        //cout<<"show "<<l<<' '<<r<<' '<<i<<'\n';
        if (l==r) return cout<<l<<' '<<d[i].mn<<' '<<d[i].f<<'\n', void();
        int md=(l+r)/2;
        pushlz(i);
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return node();
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        pushlz(i);
        return merge(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} fs;

void addrange(int l, int r)
{
    //cout<<"addrange "<<l<<' '<<r<<'\n';
    fs.update(1, n, 1, l, r, 1);
    //cout<<"after "<<fs.d[1].mn<<' '<<fs.d[1].f<<'\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    a[0]=a[n+1]=1e18;
    sm.build(1, n, 1);
    ls.build(1, n, 1);
    rs.build(1, n, 1);
    fs.build(1, n, 1);
    for (int i=1; i<=n; i++)
    {
        vector<int> p;
        rs.queryfill(1, n, 1, 1, i, sm.query(1, n, 1, 1, i), p);
        for (auto x:p) if (sm.query(1, n, 1, x, i)<a[i+1]) addrange(x, i);
    }
    //fs.show(1, n, 1);
    cin>>q;
    while (q--)
    {
        cin>>t>>l>>r;
        cout<<fs.query(1, n, 1, l, r).f<<'\n';
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17