Submission #963901

#TimeUsernameProblemLanguageResultExecution timeMemory
963901PringFish 2 (JOI22_fish2)C++17
0 / 100
11 ms3932 KiB
#include <bits/stdc++.h> 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 { int n; ll p[MXN]; void init(int _n, ll *a) { n = _n; FOR(i, 1, n + 1) p[i] = p[i - 1] + a[i]; } int 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); // BUILD(1, n + 1); // FOR(i, 1, n + 1) debug(i, L[i], R[i], hl[i], hr[i]); 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:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
fish2.cpp:91:5: note: in expansion of macro 'debug'
   91 |     debug(id);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...