Submission #1081427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081427		isaachew	Fish 2 (JOI22_fish2)	C++17	25 / 100	4091 ms	2108 KiB

fish2

#include <bits/stdc++.h>

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,q;
    std::cin>>n;
    std::vector<int> vec;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        vec.push_back(x);
    }
    std::cin>>q;
    for(;q--;){
        int a;
        std::cin>>a;
        if(a==1){
            int b,c;
            std::cin>>b>>c;
            b--;
            vec[b]=c;
        }else{
            int b,c;
            std::cin>>b>>c;
            b--;
            std::vector<long long> sums;
            std::vector<std::pair<long long,std::pair<long long,int>>> stk;//size of fish to the right, sum, number which can win
            for(int i=b;i<c;i++){
                stk.push_back({0,{0,0}});//for merging
                while(stk.size()>=2&&stk[stk.size()-2].first<vec[i]){
                    //std::cout<<"m!\n";
                    if(stk.back().second.first>=stk[stk.size()-2].first){
                        stk[stk.size()-2].second.second+=stk.back().second.second;
                    }
                    stk[stk.size()-2].second.first+=stk.back().second.first;//add sum
                    stk.pop_back();
                }
                stk.back().first=vec[i];
                stk.back().second.second=stk.back().second.first>=vec[i]?stk.back().second.second+1:1;
                stk.back().second.first+=vec[i];
            }
            while(stk.size()>=2){
                //std::cout<<"m\m";
                if(stk.back().second.first>=stk[stk.size()-2].first){
                    stk[stk.size()-2].second.second+=stk.back().second.second;
                }
                stk[stk.size()-2].second.first+=stk.back().second.first;//add sum
                stk.pop_back();
            }
            std::cout<<stk.back().second.second<<'\n';
        }
        
    }
}

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