Submission #876304

#	Time	Username	Problem	Language	Result	Execution time	Memory
876304		danikoynov	Fish 2 (JOI22_fish2)	C++14	25 / 100	4026 ms	9892 KiB

fish2

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