제출 #791846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791846		eltu0815	Fish 2 (JOI22_fish2)	C++14	25 / 100	4077 ms	8600 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];
vector<int> graph[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, mx = 0;
            for(int i = 1; i <= n; ++i) chk[i] = 0;
            for(int i = 1; i <= n; ++i) graph[i].clear();
            for(int i = a; i <= b; ++i) mx = max(mx, arr[i]);
            for(int i = a; i <= b; ++i) {
                ll tmp = sum[min(r[i], b + 1) - 1] - sum[max(l[i], a - 1)];
                if(r[i] <= b && tmp >= (ll)arr[r[i]]) graph[r[i]].push_back(i);
                if(l[i] >= a && tmp >= (ll)arr[l[i]]) graph[l[i]].push_back(i);
            }
            
            queue<int> q;
            for(int i = a; i <= b; ++i) if(arr[i] == mx) q.push(i), chk[i] = 1;
            while(!q.empty()) {
                int cur = q.front(); q.pop();
                ++ans;
                for(auto v : graph[cur]) {
                    if(!chk[v]) chk[v] = 1, q.push(v);
                }
            }
            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