Submission #963904

#	Time	Username	Problem	Language	Result	Execution time	Memory
963904		Pring	Fish 2 (JOI22_fish2)	C++17	25 / 100	4077 ms	3928 KiB

fish2

#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 100005;
int n, m, t, x, y;
ll a[MXN];
int L[MXN], R[MXN], hl[MXN], hr[MXN];

struct BIT {
    ll p[MXN];
    void init(int n, ll *a) {
        p[0] = 0;
        FOR(i, 1, n + 1) p[i] = p[i - 1] + a[i];
    }
    ll query(int l, int r) {
        return p[r] - p[l - 1];
    }
} B;

void MODIFY(int p, int v) {
    a[p] = v;
    B.init(n, a);
}

void BUILD(int l, int r) {
    vector<pii> st;
    {
        st.push_back(mp(INT_MAX, -1));
        FOR(i, l, r) {
            L[i] = -1;
            while (st.back().fs <= a[i]) {
                L[i] = st.back().sc;
                st.pop_back();
            }
            st.push_back(mp(a[i], i));
        }
        st.clear();
    }
    {
        st.push_back(mp(INT_MAX, -1));
        for (int i = r - 1; i >= l; i--) {
            R[i] = -1;
            while (st.back().fs < a[i]) {
                R[i] = st.back().sc;
                st.pop_back();
            }
            st.push_back(mp(a[i], i));
        }
        st.clear();
    }
    {
        st.push_back(mp(INT_MAX, l - 1));
        FOR(i, l, r) {
            while (st.back().fs <= a[i]) st.pop_back();
            hl[i] = st.back().sc;
            st.push_back(mp(a[i], i));
        }
        st.clear();
    }
    {
        st.push_back(mp(INT_MAX, r));
        for (int i = r - 1; i >= l; i--) {
            while (st.back().fs < a[i]) st.pop_back();
            hr[i] = st.back().sc;
            st.push_back(mp(a[i], i));
        }
        st.clear();
    }
}

void DFS(int id, int bnd, int &ans) {
    if (id == -1) return;
    debug(id);
    if (B.query(hl[id] + 1, hr[id] - 1) < bnd) return;
    ans++;
    DFS(L[id], a[id], ans);
    DFS(R[id], a[id], ans);
}

int MAX_ID(int l, int r) {
    int id = l;
    FOR(i, l + 1, r) if (a[i] >= a[id]) id = i;
    return id;
}

int QUERY(int l, int r) {
    BUILD(l, r);
    int rt = MAX_ID(l, r);
    int ans = 0;
    DFS(rt, 0, ans);
    return ans;
}

void miku() {
    cin >> n;
    FOR(i, 1, n + 1) cin >> a[i];
    B.init(n, a);
    cin >> m;
    while (m--) {
        cin >> t >> x >> y;
        if (t == 1) MODIFY(x, y);
        else cout << QUERY(x, y + 1) << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message (stderr)

fish2.cpp: In function 'void DFS(int, int, int&)':
fish2.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
fish2.cpp:92:5: note: in expansion of macro 'debug'
   92 |     debug(id);
      |     ^~~~~

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