oj.uz

Submission #791313

# Submission time Handle Problem Language Result Execution time Memory
791313 2023-07-24T01:18:20 Z eltu0815 Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 4764 KB 
#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;
    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]) j = i;
    for(int i = n; i > j; --i) ord[i] = ord[i - 1];
    ord[j] = 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(chk[li] && sumv >= lv) chk[ord[i]] = 1;
                else if(chk[ri] && sumv >= rv) chk[ord[i]] = 1;
                ans += chk[ord[i]];
            }
            cout << ans << '\n';
        }
    }
    
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 17 ms 4412 KB Output is correct
3 Correct 16 ms 4044 KB Output is correct
4 Correct 18 ms 4376 KB Output is correct
5 Correct 18 ms 4056 KB Output is correct
6 Correct 20 ms 4764 KB Output is correct
7 Correct 16 ms 4016 KB Output is correct
8 Correct 20 ms 4688 KB Output is correct
9 Correct 16 ms 4012 KB Output is correct
10 Correct 18 ms 4364 KB Output is correct
11 Correct 15 ms 4052 KB Output is correct
12 Correct 17 ms 4064 KB Output is correct
13 Correct 17 ms 4052 KB Output is correct
14 Correct 18 ms 4436 KB Output is correct
15 Correct 20 ms 4544 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 17 ms 4412 KB Output is correct
3 Correct 16 ms 4044 KB Output is correct
4 Correct 18 ms 4376 KB Output is correct
5 Correct 18 ms 4056 KB Output is correct
6 Correct 20 ms 4764 KB Output is correct
7 Correct 16 ms 4016 KB Output is correct
8 Correct 20 ms 4688 KB Output is correct
9 Correct 16 ms 4012 KB Output is correct
10 Correct 18 ms 4364 KB Output is correct
11 Correct 15 ms 4052 KB Output is correct
12 Correct 17 ms 4064 KB Output is correct
13 Correct 17 ms 4052 KB Output is correct
14 Correct 18 ms 4436 KB Output is correct
15 Correct 20 ms 4544 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Execution timed out 4066 ms 4712 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 17 ms 4412 KB Output is correct
3 Correct 16 ms 4044 KB Output is correct
4 Correct 18 ms 4376 KB Output is correct
5 Correct 18 ms 4056 KB Output is correct
6 Correct 20 ms 4764 KB Output is correct
7 Correct 16 ms 4016 KB Output is correct
8 Correct 20 ms 4688 KB Output is correct
9 Correct 16 ms 4012 KB Output is correct
10 Correct 18 ms 4364 KB Output is correct
11 Correct 15 ms 4052 KB Output is correct
12 Correct 17 ms 4064 KB Output is correct
13 Correct 17 ms 4052 KB Output is correct
14 Correct 18 ms 4436 KB Output is correct
15 Correct 20 ms 4544 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -