Submission #876131

#	Time	Username	Problem	Language	Result	Execution time	Memory
876131		danikoynov	Fish 2 (JOI22_fish2)	C++14	5 / 100	4038 ms	2908 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];


    ll last = 1, ans = 0;
    for (int i = 1; i <= len; i ++)
    {
        int lf = i - 1, rf = i + 1;
        ll sum = arr[i];
        while(lf > 0 || rf <= len)
        {
            if (lf > 0 && sum >= arr[lf])
                sum += arr[lf], lf --;
            else
            if (rf <= len && sum >= arr[rf])
                sum += arr[rf], rf ++;
            else
                break;
        }

        if (lf == 0 && rf == len + 1)
            ans ++;
    }

    cout << ans << 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;
}

Compilation message (stderr)

fish2.cpp: In function 'void solve_query(int, int)':
fish2.cpp:110:8: warning: unused variable 'last' [-Wunused-variable]
  110 |     ll last = 1, ans = 0;
      |        ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17