Submission #544510

#	Time	Username	Problem	Language	Result	Execution time	Memory
544510		model_code	Fish 2 (JOI22_fish2)	C++17	100 / 100	1784 ms	183948 KiB

fish2

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

#define INF 1000000007
using ll=long long;

struct interval{
    int l,r;
    bool operator<(const interval p)const{
        return r-l<p.r-p.l;
    }
};

struct SEG_interval{
    stack<interval>seg[1<<18];
    void add(int a,vector<interval>x){
        sort(x.begin(),x.end());
        reverse(x.begin(),x.end());
        int l=a,r=a;
        a+=(1<<17)-1;
        while(1){
            while(x.size()>0&&l<=x.back().l&&x.back().r<=r){
                seg[a].push(x.back());
                x.pop_back();
            }
            if(a==0)break;
            if(a%2==0)l-=(r-l+1);
            else r+=(r-l+1);
            a=(a-1)/2;
        }
    }
    vector<interval> erase(int a){
        vector<interval>res;
        int x=a;
        a+=(1<<17)-1;
        while(1){
            while(!seg[a].empty()&&seg[a].top().l<=x&&x<=seg[a].top().r){
                res.push_back(seg[a].top());
                seg[a].pop();
            }
            if(a==0)break;
            a=(a-1)/2;
        }
        return res;
    }
}seg_interval;

struct Node{
    int mi,cnt;
    static Node merge(const Node a,const Node b){
        Node res;
        res.mi=min(a.mi,b.mi);
        res.cnt=0;
        if(res.mi==a.mi)res.cnt+=a.cnt;
        if(res.mi==b.mi)res.cnt+=b.cnt;
        return res;
    }
};

struct SEG_count{
    Node seg[1<<18];
    int la[1<<18];
    SEG_count(){
        for(int i=(1<<18)-1;i>=0;i--){
            la[i]=0;
            if(i>=(1<<17)-1)seg[i].mi=0,seg[i].cnt=1;
            else seg[i]=Node::merge(seg[i*2+1],seg[i*2+2]);
        }
    }
    void eval(int a){
        seg[a].mi+=la[a];
        if(a<(1<<17)-1){
            la[a*2+1]+=la[a];
            la[a*2+2]+=la[a];
        }
        la[a]=0;
    }
    void add(int a,int b,int x,int k=0,int l=0,int r=(1<<17)-1){
        eval(k);
        if(b<l||r<a)return;
        if(a<=l&&r<=b){
            la[k]+=x;
            eval(k);
            return;
        }
        add(a,b,x,k*2+1,l,(l+r-1)/2);
        add(a,b,x,k*2+2,(l+r+1)/2,r);
        seg[k]=Node::merge(seg[k*2+1],seg[k*2+2]);
    }
    Node query(int a,int b,int k=0,int l=0,int r=(1<<17)-1){
        eval(k);
        if(b<l||r<a)return Node{INF,1};
        if(a<=l&&r<=b)return seg[k];
        return Node::merge(query(a,b,k*2+1,l,(l+r-1)/2),query(a,b,k*2+2,(l+r+1)/2,r));
    }
}seg_count;

struct SEG_others{
    ll sum[1<<18];
    int ma[1<<18];
    SEG_others(){
        for(int i=0;i<1<<18;i++)sum[i]=0,ma[i]=0;
    }
    void update(int a,int x){
        a+=(1<<17)-1;
        sum[a]=x;
        ma[a]=x;
        while(a>0){
            a=(a-1)/2;
            sum[a]=sum[a*2+1]+sum[a*2+2];
            ma[a]=max(ma[a*2+1],ma[a*2+2]);
        }
    }
    ll query_sum(int a,int b,int k=0,int l=0,int r=(1<<17)-1){
        if(b<l||r<a)return 0;
        if(a<=l&&r<=b)return sum[k];
        return query_sum(a,b,k*2+1,l,(l+r-1)/2)+query_sum(a,b,k*2+2,(l+r+1)/2,r);
    }
    int leftest(int a,int x,int k=0,int l=0,int r=(1<<17)-1){
        if(r<a||ma[k]<=x)return -1;
        if(l==r)return l;
        if(ma[k*2+1]>x){
            int res=leftest(a,x,k*2+1,l,(l+r-1)/2);
            if(res!=-1)return res;
        }
        return leftest(a,x,k*2+2,(l+r+1)/2,r);
    }
    int rightest(int a,int x,int k=0,int l=0,int r=(1<<17)-1){
        if(a<l||ma[k]<=x)return -1;
        if(l==r)return l;
        if(ma[k*2+2]>x){
            int res=rightest(a,x,k*2+2,(l+r+1)/2,r);
            if(res!=-1)return res;
        }
        return rightest(a,x,k*2+1,l,(l+r-1)/2);
    }
}seg_others;

int n,A[100005];

vector<pair<int,ll>>right_cand(int a){
    vector<pair<int,ll>>res;
    ll s=A[a];
    while(a<n){
        a++;
        int nxt=seg_others.leftest(a,s);
        if(nxt==-1)break;
        res.push_back(make_pair(nxt,seg_others.query_sum(0,nxt)));
        s+=A[nxt];
        a=nxt;
    }
    return res;
}

vector<pair<int,ll>>left_cand(int a){
    vector<pair<int,ll>>res;
    ll s=A[a];
    while(a>1){
        a--;
        int nxt=seg_others.rightest(a,s);
        if(nxt==-1)break;
        res.push_back(make_pair(nxt,seg_others.query_sum(0,nxt)));
        s+=A[nxt];
        a=nxt;
    }
    return res;
}

void update(int a,int x){
    for(int i=-1;i<=1;i++){
        vector<interval>del=seg_interval.erase(a+i);
        for(auto j:del)seg_count.add(j.l,j.r,-1);
    }
    A[a]=x;
    seg_others.update(a,x);
    vector<pair<int,ll>>right=right_cand(a+1);
    right.push_back(make_pair(a,seg_others.query_sum(0,a)));
    right.push_back(make_pair(a+1,seg_others.query_sum(0,a+1)));
    vector<pair<int,ll>>left=left_cand(a-1);
    left.push_back(make_pair(a,seg_others.query_sum(0,a)));
    left.push_back(make_pair(a-1,seg_others.query_sum(0,a-1)));
    vector<interval>_bad,bad,bad_;
    for(auto i:left){
        for(auto j:right){
            int l=i.first,r=j.first;
            if(l>=r-1)continue;
            ll s=j.second-A[r]-i.second;
            if(s<A[l]&&s<A[r]){
                l++,r--;
                seg_count.add(l,r,1);
                if(l<=a&&a<=r)bad.push_back(interval{l,r});
                else if(l<=a-1&&a-1<=r)_bad.push_back(interval{l,r});
                else bad_.push_back(interval{l,r});
            }
        }
    }
    seg_interval.add(a-1,_bad);
    seg_interval.add(a+1,bad_);
    seg_interval.add(a,bad);
}

int query(int l,int r){
    ll l_sum=seg_others.query_sum(0,l-1);
    vector<pair<int,ll>>right=right_cand(l);
    for(auto i:right){
        if(i.second-l_sum-A[i.first]<A[i.first]&&i.first<=r)l=max(l,i.first);
    }
    ll r_sum=seg_others.query_sum(0,r);
    vector<pair<int,ll>>left=left_cand(r);
    for(auto i:left){
        if(r_sum-i.second<A[i.first]&&i.first>=l)r=min(r,i.first);
    }
    return seg_count.query(l,r).cnt;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>A[i];
        update(i,A[i]);
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int a,x;
            cin>>a>>x;
            update(a,x);
        }else{
            int l,r;
            cin>>l>>r;
            cout<<query(l,r)<<endl;
        }
    }
}

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