Submission #727751

#	Time	Username	Problem	Language	Result	Execution time	Memory
727751		fatemetmhr	Fish 2 (JOI22_fish2)	C++17	25 / 100	944 ms	2900 KiB

fish2

// Be name khoda //

#include <bits/stdc++.h>


using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair

const int maxn5 = 1e5 + 10;
const int maxnt = 4e6 + 10;
const ll  inf   = 1e18;

int cnt[maxn5], a[maxn5], av[maxn5], lq, rq;
ll ps[maxn5];

inline void check(int l, int r){
    if(r == l + 1)
        return;
    ll sum = ps[r - 1] - (l == -1 ? 0 : ps[l]);
    //cout << "checking " << l << ' ' << r << ' ' << sum << endl;
    if(sum >= min(r >= rq ? inf : a[r], l < lq ? inf : a[l]))
        return;
    //cout << "ya " << l << ' ' << r << endl;
    cnt[l + 1]++;
    cnt[r]--;
}


inline void solve1(int n, int q){

    ios_base::sync_with_stdio(false); cin.tie(0);

    ps[0] = a[0];
    for(int i = 1; i < n; i++)
        ps[i] = ps[i - 1] + a[i];

    while(q--){
        int ty, l, r; cin >> ty >> l >> r;
        l--;
        if(ty == 1){
            a[l] = r;
            ps[0] = a[0];
            for(int i = 1; i < n; i++)
                ps[i] = ps[i - 1] + a[i];
        }
        else{
            int pt = 0;
            lq = l; rq = r;
            memset(cnt, 0, sizeof cnt);
            for(int i = l; i < r; i++){
                while(pt && a[av[pt - 1]] < a[i]){
                    check(av[pt - 1], i);
                    pt--;
                }
                //cout << "ok " << i << ' ' << pt << ' ' << (pt ? av[pt - 1] : lq - 1) << ' ' << a[5] << ' ' << a[i] << endl;
                check(pt ? av[pt - 1] : lq - 1, i);
                av[pt++] = i;
            }
            for(int i = 0; i < pt; i++)
                check(av[i], rq);
            int cur = 0, ans = 0;
            for(int i = l; i < r; i++){
                cur += cnt[i];
                if(!cur)
                    ans++;
            }
            cout << ans << '\n';
        }
    }
}

inline void solve2(int n, int q){

}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int q; cin >> q;
    if(q <= 1000)
        solve1(n, q);
    else
        solve2(n, q);

}

/*
5
6 4 2 2 6
1
2 1 5
2 1 3
1 3 1
2 2 5
2 1 5
2 2 4
*/

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