Submission #876129

#	Time	Username	Problem	Language	Result	Execution time	Memory
876129		danikoynov	Fish 2 (JOI22_fish2)	C++14	0 / 100	0 ms	464 KiB

fish2

#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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17