oj.uz

Submission #754928

# Submission time Handle Problem Language Result Execution time Memory
754928 2023-06-08T22:41:16 Z definitelynotmee Fish 2 (JOI22_fish2) C++17
25 / 100
 4000 ms 5468 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

const ll INFL = 1E18;
int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;

    vector<ll> in(n);

    for(ll & i : in)
        cin >> i;

    int q;
    cin >> q;

    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        l--;
        if(t== 1){
            in[l] = r;
        } else {
            vector<ll> v(in.begin()+l,in.begin()+r);
            v.insert(v.begin(),INFL);
            v.push_back(INFL-1);

            int n = v.size();
            vector<int> jmp(n);
            vector<ll> psum(n);

            for(int i = 1; i < n; i++)
                psum[i] = psum[i-1]+v[i];

            vector<int> delta(n);

            auto make_ban =[&](int l, int r){
                if(v[r] > psum[r-1]-psum[l] && v[l] > psum[r-1]-psum[l] && l + 1 < r){
                    delta[l+1]++;
                    delta[r]--;
                }
            };

            for(int i = 1; i < n; i++){
                jmp[i] = i-1;
                while(v[jmp[i]] <= v[i]){
                    make_ban(jmp[i],i);
                    jmp[i] = jmp[jmp[i]];
                }
                if(i != n-1)
                    make_ban(jmp[i],i);
            }
            int resp = 0, cur = 0;
            for(int i = 1; i < n-1; i++){
                cur+=delta[i];
                if(cur == 0)
                    resp++;
            }
            cout << resp << '\n';
        }
    }




}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 420 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 328 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 3 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 11 ms 3960 KB Output is correct
3 Correct 10 ms 3768 KB Output is correct
4 Correct 12 ms 4036 KB Output is correct
5 Correct 9 ms 3792 KB Output is correct
6 Correct 14 ms 4420 KB Output is correct
7 Correct 9 ms 3612 KB Output is correct
8 Correct 14 ms 4408 KB Output is correct
9 Correct 8 ms 3644 KB Output is correct
10 Correct 11 ms 4028 KB Output is correct
11 Correct 8 ms 3652 KB Output is correct
12 Correct 9 ms 3652 KB Output is correct
13 Correct 8 ms 3652 KB Output is correct
14 Correct 11 ms 4032 KB Output is correct
15 Correct 12 ms 4036 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 420 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 328 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 3 ms 340 KB Output is correct
21 Correct 0 ms 320 KB Output is correct
22 Correct 11 ms 3960 KB Output is correct
23 Correct 10 ms 3768 KB Output is correct
24 Correct 12 ms 4036 KB Output is correct
25 Correct 9 ms 3792 KB Output is correct
26 Correct 14 ms 4420 KB Output is correct
27 Correct 9 ms 3612 KB Output is correct
28 Correct 14 ms 4408 KB Output is correct
29 Correct 8 ms 3644 KB Output is correct
30 Correct 11 ms 4028 KB Output is correct
31 Correct 8 ms 3652 KB Output is correct
32 Correct 9 ms 3652 KB Output is correct
33 Correct 8 ms 3652 KB Output is correct
34 Correct 11 ms 4032 KB Output is correct
35 Correct 12 ms 4036 KB Output is correct
36 Correct 199 ms 5028 KB Output is correct
37 Correct 336 ms 4604 KB Output is correct
38 Correct 356 ms 4684 KB Output is correct
39 Correct 91 ms 4476 KB Output is correct
40 Correct 431 ms 5032 KB Output is correct
41 Correct 436 ms 5388 KB Output is correct
42 Correct 564 ms 5448 KB Output is correct
43 Correct 436 ms 4744 KB Output is correct
44 Correct 491 ms 4592 KB Output is correct
45 Correct 194 ms 5120 KB Output is correct
46 Correct 282 ms 5052 KB Output is correct
47 Correct 419 ms 4904 KB Output is correct
48 Correct 173 ms 4540 KB Output is correct
49 Correct 551 ms 4684 KB Output is correct
50 Correct 290 ms 5152 KB Output is correct
51 Correct 1614 ms 4860 KB Output is correct
52 Correct 1764 ms 5108 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 11 ms 3960 KB Output is correct
3 Correct 10 ms 3768 KB Output is correct
4 Correct 12 ms 4036 KB Output is correct
5 Correct 9 ms 3792 KB Output is correct
6 Correct 14 ms 4420 KB Output is correct
7 Correct 9 ms 3612 KB Output is correct
8 Correct 14 ms 4408 KB Output is correct
9 Correct 8 ms 3644 KB Output is correct
10 Correct 11 ms 4028 KB Output is correct
11 Correct 8 ms 3652 KB Output is correct
12 Correct 9 ms 3652 KB Output is correct
13 Correct 8 ms 3652 KB Output is correct
14 Correct 11 ms 4032 KB Output is correct
15 Correct 12 ms 4036 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 4043 ms 5468 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 11 ms 3960 KB Output is correct
3 Correct 10 ms 3768 KB Output is correct
4 Correct 12 ms 4036 KB Output is correct
5 Correct 9 ms 3792 KB Output is correct
6 Correct 14 ms 4420 KB Output is correct
7 Correct 9 ms 3612 KB Output is correct
8 Correct 14 ms 4408 KB Output is correct
9 Correct 8 ms 3644 KB Output is correct
10 Correct 11 ms 4028 KB Output is correct
11 Correct 8 ms 3652 KB Output is correct
12 Correct 9 ms 3652 KB Output is correct
13 Correct 8 ms 3652 KB Output is correct
14 Correct 11 ms 4032 KB Output is correct
15 Correct 12 ms 4036 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 4050 ms 5144 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 420 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 328 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 3 ms 340 KB Output is correct
21 Correct 0 ms 320 KB Output is correct
22 Correct 11 ms 3960 KB Output is correct
23 Correct 10 ms 3768 KB Output is correct
24 Correct 12 ms 4036 KB Output is correct
25 Correct 9 ms 3792 KB Output is correct
26 Correct 14 ms 4420 KB Output is correct
27 Correct 9 ms 3612 KB Output is correct
28 Correct 14 ms 4408 KB Output is correct
29 Correct 8 ms 3644 KB Output is correct
30 Correct 11 ms 4028 KB Output is correct
31 Correct 8 ms 3652 KB Output is correct
32 Correct 9 ms 3652 KB Output is correct
33 Correct 8 ms 3652 KB Output is correct
34 Correct 11 ms 4032 KB Output is correct
35 Correct 12 ms 4036 KB Output is correct
36 Correct 199 ms 5028 KB Output is correct
37 Correct 336 ms 4604 KB Output is correct
38 Correct 356 ms 4684 KB Output is correct
39 Correct 91 ms 4476 KB Output is correct
40 Correct 431 ms 5032 KB Output is correct
41 Correct 436 ms 5388 KB Output is correct
42 Correct 564 ms 5448 KB Output is correct
43 Correct 436 ms 4744 KB Output is correct
44 Correct 491 ms 4592 KB Output is correct
45 Correct 194 ms 5120 KB Output is correct
46 Correct 282 ms 5052 KB Output is correct
47 Correct 419 ms 4904 KB Output is correct
48 Correct 173 ms 4540 KB Output is correct
49 Correct 551 ms 4684 KB Output is correct
50 Correct 290 ms 5152 KB Output is correct
51 Correct 1614 ms 4860 KB Output is correct
52 Correct 1764 ms 5108 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Execution timed out 4043 ms 5468 KB Time limit exceeded
55 Halted 0 ms 0 KB -