Submission #791706

#	Time	Username	Problem	Language	Result	Execution time	Memory
791706		eltu0815	Fish 2 (JOI22_fish2)	C++14	25 / 100	4057 ms	4856 KiB

fish2

#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define inf (1987654321)
 
using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
int n, q;
int arr[100005], l[100005], r[100005], ord[100005], chk[100005];
ll sum[100005];
pii tmp[100005];

void update_sum() {
    for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + arr[i];
}

void update_sort(int idx) {
    int j = 0, k = 0;
    for(int i = 1; i <= n; ++i) if(ord[i] == idx) j = i;
    for(int i = j; i < n; ++i) ord[i] = ord[i + 1];
    for(int i = 1; i < n; ++i) if(arr[ord[i]] >= arr[idx]) k = i;
    for(int i = n; i > k + 1; --i) ord[i] = ord[i - 1];
    ord[k + 1] = idx;
}

void update_r() {
    stack<int> st;
    for(int i = 1; i <= n; ++i) r[i] = n + 1;
    for(int i = 1; i <= n; ++i) {
        while(!st.empty() && arr[st.top()] < arr[i]) {
            r[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
}

void update_l() {
    stack<int> st;
    for(int i = 1; i <= n; ++i) l[i] = 0;
    for(int i = n; i >= 1; --i) {
        while(!st.empty() && arr[st.top()] < arr[i]) {
            l[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> arr[i];
    for(int i = 1; i <= n; ++i) tmp[i] = {arr[i], i};
    sort(tmp + 1, tmp + n + 1, greater<pii>());
    for(int i = 1; i <= n; ++i) ord[i] = tmp[i].second;
    update_sum(); update_l(); update_r();
    
    cin >> q;
    while(q--) {
        int t, a, b; cin >> t >> a >> b;
        if(t == 1) {
            arr[a] = b;
            update_sum(); update_l(); update_r();
            update_sort(a);
        }
        else {
            int ans = 0;
            for(int i = 1; i <= n; ++i) chk[i] = 0;
            for(int i = 1; i <= n; ++i) {
                if(ord[i] < a || ord[i] > b) continue;
                int lv = l[ord[i]] >= a ? arr[l[ord[i]]] : inf, li = max(l[ord[i]], a - 1);
                int rv = r[ord[i]] <= b ? arr[r[ord[i]]] : inf, ri = min(r[ord[i]], b + 1);
                ll sumv = sum[ri - 1] - sum[li];
                if(lv == inf && rv == inf) chk[ord[i]] = 1;
                else if(lv <= rv && lv != -1 && chk[li] && sumv >= lv) chk[ord[i]] = 1;
                else if(rv <= lv && rv != -1 && chk[ri] && sumv >= rv) chk[ord[i]] = 1;
                ans += chk[ord[i]];
            }
            cout << ans << '\n';
        }
    }
    
    return 0;
}

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