oj.uz

Submission #876304

# Submission time Handle Problem Language Result Execution time Memory
876304 2023-11-21T14:11:35 Z danikoynov Fish 2 (JOI22_fish2) C++14
25 / 100
 4000 ms 9892 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;


int n, q;
ll a[maxn], pref[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    cin >> q;
    a[0] = 1e9 + 10;
    a[n + 1] = 1e9 + 10;

}

vector < pair < int, int > > ranges;
void get_ranges()
{

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

    ranges.clear();
    stack < int > st;
    st.push(0);
    for (int i = 1; i <= n; i ++)
    {
        while(!st.empty() && a[st.top()] < a[i])
            st.pop();


        if (pref[i - 1] - pref[st.top()] < a[i])
            ranges.push_back({st.top() + 1, i - 1});

        st.push(i);
    }

    while(!st.empty())
        st.pop();
    st.push(n + 1);
    for (int i = n; i > 0; i --)
    {
        while(!st.empty() && a[st.top()] < a[i])
            st.pop();

        if (pref[st.top() - 1] - pref[i] < a[i])
            ranges.push_back({i + 1, st.top() - 1});

        st.push(i);
    }
}

int b[maxn];

struct node
{
    int cnt, mx;

    node(int _cnt = 0, int _mx = 1e9 + 10)
    {
        cnt = _cnt;
        mx = _mx;
    }
};

node tree[4 * maxn];

node merge_node(node lf, node rf)
{
    if (lf.cnt == -1 || rf.mx < lf.mx)
        return rf;
    if (rf.cnt == -1 || lf.mx < rf.mx)
        return lf;

    return node(lf.cnt + rf.cnt, lf.mx);
}

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].mx = b[left];
        tree[root].cnt = 1;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return node(-1, 1e9 + 10);

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;

    return merge_node(query(root * 2, left, mid, qleft, qright),
            query(root * 2 + 1, mid + 1, right, qleft, qright));
}

void solve_query(int left, int right)
{

    //for (pair < int, int > cur : ranges)
      //  cout << cur.first << " : " << cur.second << endl;

    int lb = left, rb = right;
    for (int i = left; i <= right; i ++)
    {
        if (a[i] > pref[i - 1] - pref[left - 1])
            lb = max(lb, i);
        if (a[i] > pref[right] - pref[i])
            rb = min(rb, i);
    }

    /**int minx = 1e9;
    for (int i = lb; i <= rb; i ++)
        minx = min(minx, b[i]);

    int ans = 0;
    for (int i = lb; i <= rb; i ++)
        if (b[i] == minx)
        ans ++;*/

    cout << query(1, 1, n, lb, rb).cnt << endl;
}
void simulate()
{
    get_ranges();
    for (int i = 1; i <= n; i ++)
        b[i] = 0;
    for (pair < int, int > cur : ranges)
        for (int i = cur.first; i <= cur.second; i ++)
        b[i] ++;
    build_tree(1, 1, n);
    for (int i = 1; i <= q; i ++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int idx;
            ll x;
            cin >> idx >> x;
            a[idx] = x;
            get_ranges();
            for (int i = 1; i <= n; i ++)
                b[i] = 0;
            for (pair < int, int > cur : ranges)
                for (int i = cur.first; i <= cur.second; i ++)
                b[i] ++;
            build_tree(1, 1, n);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            solve_query(l, r);
        }
    }
}
void solve()
{
    input();
    simulate();
}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    speed();
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4704 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 7 ms 4700 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 7 ms 4764 KB Output is correct
8 Correct 4 ms 4700 KB Output is correct
9 Correct 3 ms 4696 KB Output is correct
10 Correct 5 ms 4696 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 7 ms 4700 KB Output is correct
13 Correct 3 ms 4704 KB Output is correct
14 Correct 7 ms 4764 KB Output is correct
15 Correct 5 ms 4700 KB Output is correct
16 Correct 3 ms 4700 KB Output is correct
17 Correct 6 ms 4764 KB Output is correct
18 Correct 2 ms 4700 KB Output is correct
19 Correct 5 ms 4700 KB Output is correct
20 Correct 3 ms 4696 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 11 ms 7516 KB Output is correct
3 Correct 14 ms 7640 KB Output is correct
4 Correct 12 ms 7556 KB Output is correct
5 Correct 11 ms 7640 KB Output is correct
6 Correct 14 ms 7640 KB Output is correct
7 Correct 10 ms 7744 KB Output is correct
8 Correct 14 ms 7636 KB Output is correct
9 Correct 10 ms 7636 KB Output is correct
10 Correct 12 ms 7636 KB Output is correct
11 Correct 11 ms 7640 KB Output is correct
12 Correct 11 ms 7668 KB Output is correct
13 Correct 11 ms 7640 KB Output is correct
14 Correct 13 ms 7636 KB Output is correct
15 Correct 13 ms 7572 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4704 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 7 ms 4700 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 7 ms 4764 KB Output is correct
8 Correct 4 ms 4700 KB Output is correct
9 Correct 3 ms 4696 KB Output is correct
10 Correct 5 ms 4696 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 7 ms 4700 KB Output is correct
13 Correct 3 ms 4704 KB Output is correct
14 Correct 7 ms 4764 KB Output is correct
15 Correct 5 ms 4700 KB Output is correct
16 Correct 3 ms 4700 KB Output is correct
17 Correct 6 ms 4764 KB Output is correct
18 Correct 2 ms 4700 KB Output is correct
19 Correct 5 ms 4700 KB Output is correct
20 Correct 3 ms 4696 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct
22 Correct 11 ms 7516 KB Output is correct
23 Correct 14 ms 7640 KB Output is correct
24 Correct 12 ms 7556 KB Output is correct
25 Correct 11 ms 7640 KB Output is correct
26 Correct 14 ms 7640 KB Output is correct
27 Correct 10 ms 7744 KB Output is correct
28 Correct 14 ms 7636 KB Output is correct
29 Correct 10 ms 7636 KB Output is correct
30 Correct 12 ms 7636 KB Output is correct
31 Correct 11 ms 7640 KB Output is correct
32 Correct 11 ms 7668 KB Output is correct
33 Correct 11 ms 7640 KB Output is correct
34 Correct 13 ms 7636 KB Output is correct
35 Correct 13 ms 7572 KB Output is correct
36 Correct 1746 ms 7892 KB Output is correct
37 Correct 1193 ms 7640 KB Output is correct
38 Correct 227 ms 7636 KB Output is correct
39 Correct 2592 ms 7640 KB Output is correct
40 Correct 234 ms 7640 KB Output is correct
41 Correct 1344 ms 7640 KB Output is correct
42 Correct 528 ms 7640 KB Output is correct
43 Correct 1322 ms 7640 KB Output is correct
44 Correct 459 ms 7640 KB Output is correct
45 Correct 1769 ms 7640 KB Output is correct
46 Correct 1115 ms 7636 KB Output is correct
47 Correct 238 ms 7640 KB Output is correct
48 Correct 3065 ms 7644 KB Output is correct
49 Correct 473 ms 7640 KB Output is correct
50 Correct 1672 ms 7900 KB Output is correct
51 Correct 1419 ms 7644 KB Output is correct
52 Correct 273 ms 7644 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 11 ms 7516 KB Output is correct
3 Correct 14 ms 7640 KB Output is correct
4 Correct 12 ms 7556 KB Output is correct
5 Correct 11 ms 7640 KB Output is correct
6 Correct 14 ms 7640 KB Output is correct
7 Correct 10 ms 7744 KB Output is correct
8 Correct 14 ms 7636 KB Output is correct
9 Correct 10 ms 7636 KB Output is correct
10 Correct 12 ms 7636 KB Output is correct
11 Correct 11 ms 7640 KB Output is correct
12 Correct 11 ms 7668 KB Output is correct
13 Correct 11 ms 7640 KB Output is correct
14 Correct 13 ms 7636 KB Output is correct
15 Correct 13 ms 7572 KB Output is correct
16 Correct 1 ms 4952 KB Output is correct
17 Correct 3329 ms 8360 KB Output is correct
18 Correct 3229 ms 9720 KB Output is correct
19 Correct 3186 ms 9020 KB Output is correct
20 Correct 3275 ms 9412 KB Output is correct
21 Correct 3375 ms 9384 KB Output is correct
22 Correct 3187 ms 9456 KB Output is correct
23 Correct 3317 ms 9452 KB Output is correct
24 Correct 3210 ms 9496 KB Output is correct
25 Correct 3412 ms 9204 KB Output is correct
26 Correct 3226 ms 9264 KB Output is correct
27 Correct 3195 ms 9684 KB Output is correct
28 Correct 3246 ms 9892 KB Output is correct
29 Correct 3243 ms 9892 KB Output is correct
30 Correct 3196 ms 8804 KB Output is correct
31 Correct 3445 ms 8624 KB Output is correct
32 Correct 3251 ms 9260 KB Output is correct
33 Correct 3259 ms 9468 KB Output is correct
34 Correct 3249 ms 8920 KB Output is correct
35 Correct 3318 ms 9260 KB Output is correct
36 Correct 3254 ms 9568 KB Output is correct
37 Correct 3625 ms 8664 KB Output is correct
38 Correct 3188 ms 8660 KB Output is correct
39 Correct 3290 ms 9668 KB Output is correct
40 Execution timed out 4026 ms 8568 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 11 ms 7516 KB Output is correct
3 Correct 14 ms 7640 KB Output is correct
4 Correct 12 ms 7556 KB Output is correct
5 Correct 11 ms 7640 KB Output is correct
6 Correct 14 ms 7640 KB Output is correct
7 Correct 10 ms 7744 KB Output is correct
8 Correct 14 ms 7636 KB Output is correct
9 Correct 10 ms 7636 KB Output is correct
10 Correct 12 ms 7636 KB Output is correct
11 Correct 11 ms 7640 KB Output is correct
12 Correct 11 ms 7668 KB Output is correct
13 Correct 11 ms 7640 KB Output is correct
14 Correct 13 ms 7636 KB Output is correct
15 Correct 13 ms 7572 KB Output is correct
16 Correct 1 ms 4696 KB Output is correct
17 Execution timed out 4014 ms 7636 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 4700 KB Output is correct
2 Correct 1 ms 4704 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 7 ms 4700 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 7 ms 4764 KB Output is correct
8 Correct 4 ms 4700 KB Output is correct
9 Correct 3 ms 4696 KB Output is correct
10 Correct 5 ms 4696 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 7 ms 4700 KB Output is correct
13 Correct 3 ms 4704 KB Output is correct
14 Correct 7 ms 4764 KB Output is correct
15 Correct 5 ms 4700 KB Output is correct
16 Correct 3 ms 4700 KB Output is correct
17 Correct 6 ms 4764 KB Output is correct
18 Correct 2 ms 4700 KB Output is correct
19 Correct 5 ms 4700 KB Output is correct
20 Correct 3 ms 4696 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct
22 Correct 11 ms 7516 KB Output is correct
23 Correct 14 ms 7640 KB Output is correct
24 Correct 12 ms 7556 KB Output is correct
25 Correct 11 ms 7640 KB Output is correct
26 Correct 14 ms 7640 KB Output is correct
27 Correct 10 ms 7744 KB Output is correct
28 Correct 14 ms 7636 KB Output is correct
29 Correct 10 ms 7636 KB Output is correct
30 Correct 12 ms 7636 KB Output is correct
31 Correct 11 ms 7640 KB Output is correct
32 Correct 11 ms 7668 KB Output is correct
33 Correct 11 ms 7640 KB Output is correct
34 Correct 13 ms 7636 KB Output is correct
35 Correct 13 ms 7572 KB Output is correct
36 Correct 1746 ms 7892 KB Output is correct
37 Correct 1193 ms 7640 KB Output is correct
38 Correct 227 ms 7636 KB Output is correct
39 Correct 2592 ms 7640 KB Output is correct
40 Correct 234 ms 7640 KB Output is correct
41 Correct 1344 ms 7640 KB Output is correct
42 Correct 528 ms 7640 KB Output is correct
43 Correct 1322 ms 7640 KB Output is correct
44 Correct 459 ms 7640 KB Output is correct
45 Correct 1769 ms 7640 KB Output is correct
46 Correct 1115 ms 7636 KB Output is correct
47 Correct 238 ms 7640 KB Output is correct
48 Correct 3065 ms 7644 KB Output is correct
49 Correct 473 ms 7640 KB Output is correct
50 Correct 1672 ms 7900 KB Output is correct
51 Correct 1419 ms 7644 KB Output is correct
52 Correct 273 ms 7644 KB Output is correct
53 Correct 1 ms 4952 KB Output is correct
54 Correct 3329 ms 8360 KB Output is correct
55 Correct 3229 ms 9720 KB Output is correct
56 Correct 3186 ms 9020 KB Output is correct
57 Correct 3275 ms 9412 KB Output is correct
58 Correct 3375 ms 9384 KB Output is correct
59 Correct 3187 ms 9456 KB Output is correct
60 Correct 3317 ms 9452 KB Output is correct
61 Correct 3210 ms 9496 KB Output is correct
62 Correct 3412 ms 9204 KB Output is correct
63 Correct 3226 ms 9264 KB Output is correct
64 Correct 3195 ms 9684 KB Output is correct
65 Correct 3246 ms 9892 KB Output is correct
66 Correct 3243 ms 9892 KB Output is correct
67 Correct 3196 ms 8804 KB Output is correct
68 Correct 3445 ms 8624 KB Output is correct
69 Correct 3251 ms 9260 KB Output is correct
70 Correct 3259 ms 9468 KB Output is correct
71 Correct 3249 ms 8920 KB Output is correct
72 Correct 3318 ms 9260 KB Output is correct
73 Correct 3254 ms 9568 KB Output is correct
74 Correct 3625 ms 8664 KB Output is correct
75 Correct 3188 ms 8660 KB Output is correct
76 Correct 3290 ms 9668 KB Output is correct
77 Execution timed out 4026 ms 8568 KB Time limit exceeded
78 Halted 0 ms 0 KB -