oj.uz

Submission #876129

# Submission time Handle Problem Language Result Execution time Memory
876129 2023-11-21T09:48:49 Z danikoynov Fish 2 (JOI22_fish2) C++14
0 / 100
 0 ms 464 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;
struct Treap
{
    struct Node
    {
        ll key;
        int pr, sz;
        Node *lf, *rf;

        Node(ll _key)
        {
            key = _key;
            pr = rand();
            lf = rf = NULL;
        }

        void con()
        {
            sz = 1;
            if (lf) sz = sz + lf -> sz;
            if (rf) sz = sz + rf -> sz;
        }
    };

    Node *root;

    void Split(Node *T, Node *&L, Node *&R, ll value)
    {
        if (T == NULL)
        {
            L = R = NULL;
            return;
        }

        if (T -> key <= value)
        {
            L = T;
            Split(T -> rf, L -> rf, R, value);
        }
        else
        {
            R = T;
            Split(T -> lf, L, R -> lf, value);
        }

        T -> con();
    }

    void Merge(Node *&T, Node *L, Node *R)
    {
        if (L == NULL && R == NULL)
        {
            T = NULL;
            return;
        }

        if (L == NULL)
        {
            T = R;
            return;
        }

        if (R == NULL)
        {
            T = L;
            return;
        }

        if (L -> pr > R -> pr)
        {
            T = L;
            Merge(T -> rf, L -> rf, R);
        }
        else
        {
            T = R;
            Merge(T -> lf, L, R -> lf);
        }

        T -> con();
    }
};

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

}

ll arr[maxn];
void solve_query(int l, int r)
{
    int len = r - l + 1;
    for (int i = l; i <= r; i ++)
        arr[i - l + 1] = a[i];

    sort(arr + 1, arr + len + 1);
    ll last = 1, pref = 0;
    for (int i = 1; i <= len; i ++)
    {
        if (arr[i] > pref)
            last = i;
        pref = pref + arr[i];
    }

    cout << len - last + 1 << endl;
}

void simulate()
{
    for (int i = 1; i <= q; i ++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int idx;
            ll x;
            cin >> idx >> x;
            a[idx] = x;
        }
        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
0 / 5.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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