Submission #1017450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017450		isaachew	Fish 3 (JOI24_fish3)	C++17	100 / 100	257 ms	37696 KiB

Main

#include <bits/stdc++.h>
/*
 Suffix add 1 or point increase by D
 D=1: do as many suffix increases as possible with Cartesian tree
 D>1: suffix pattern must be same mod D
 Ignore the mod D part by shifting the values to implicitly include the mod D part
 */
struct segtree{
    int size;
    std::vector<std::pair<long long,int>> nodes;
    segtree(int n){
        size=n;
        nodes.resize(2*n-1,{1e18,-1});
    }
    void init(std::vector<long long>& vec,int nl,int nr,int ni){
        if(nl+1>=nr){
            nodes[ni]={vec[nl],nl};
        }else{
            int nm=(nl+nr)/2;
            init(vec,nl,nm,ni+1);
            init(vec,nm,nr,ni+2*(nm-nl));
            nodes[ni]=std::min(nodes[ni+1],nodes[ni+2*(nm-nl)]);
        }
    }
    std::pair<long long,int> query(int l,int r,int nl,int nr,int ni){
        if(r<=nl||l>=nr)return {1e18,-1};
        if(l<=nl&&r>=nr)return nodes[ni];
        int nm=(nl+nr)/2;
        return std::min(query(l,r,nl,nm,ni+1),query(l,r,nm,nr,ni+2*(nm-nl)));
    }
    std::pair<long long,int> query(int l,int r){
        return query(l,r,0,size,0);
    }
};
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    long long n,d;
    std::cin>>n>>d;
    std::vector<long long> vals,shifts,newvals;
    for(int i=0;i<n;i++){
        long x;
        std::cin>>x;
        vals.push_back(x);
        if(i)shifts.push_back(shifts.back()+((x-vals[i-1])%d+d)%d);
        else shifts.push_back(x%d);
        newvals.push_back(vals.back()-shifts.back());
    }
    segtree rmin(n);
    rmin.init(newvals,0,n,0);
    std::vector<long long> cdp(1,0);//can underflow but don't care
    std::vector<int> cinds(1,0);
    std::vector<long long> cpsums(1,0);//can underflow
    for(int i=1;i<=n;i++){
        while(cinds.back()!=0&&newvals[cinds.back()-1]>newvals[i-1])cinds.pop_back();
        cdp.push_back(cdp[cinds.back()]+(i-cinds.back())*newvals[i-1]);
        cinds.push_back(i);
    }
    for(int i=0;i<n;i++){
        cpsums.push_back(cpsums.back()+newvals[i]);
    }
    int q;
    std::cin>>q;
    while(q--){
        int a,b;
        std::cin>>a>>b;
        a--;
        std::pair<long long,int> curmin=rmin.query(a,b);
        if(curmin.first+shifts[a]<0)std::cout<<"-1\n";
        else{
            long long btype=cdp[b]-cdp[curmin.second+1]+curmin.first*(curmin.second+1-a);
            long long atype=((cpsums[b]-cpsums[a])-btype)/d;
            std::cout<<atype<<'\n';
        }
        
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36