Submission #568860

#TimeUsernameProblemLanguageResultExecution timeMemory
568860maomao90Fish 2 (JOI22_fish2)C++17
13 / 100
4094 ms5192 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} #define REP(i, s, e) for (int i = s; i < e; i++) #define RREP(i, s, e) for (int i = s; i >= e; i--) typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 200005; int n; int a[MAXN]; int q; ll sm[MAXN * 4]; ii mx[MAXN * 4]; #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1 void upd(int i, int x, int u = 1, int lo = 1, int hi = n) { if (lo == hi) { sm[u] = x; mx[u] = {x, lo}; return; } MLR; if (i <= mid) { upd(i, x, lc, lo, mid); } else { upd(i, x, rc, mid + 1, hi); } sm[u] = sm[lc] + sm[rc]; mx[u] = max(mx[lc], mx[rc]); } ll qsm(int s, int e, int u = 1, int lo = 1, int hi = n) { if (lo >= s && hi <= e) { return sm[u]; } MLR; ll res = 0; if (s <= mid) { res += qsm(s, e, lc, lo, mid); } if (e > mid) { res += qsm(s, e, rc, mid + 1, hi); } return res; } ii qmx(int s, int e, int u = 1, int lo = 1, int hi = n) { if (lo >= s && hi <= e) { return mx[u]; } MLR; ii res = {-1, -1}; if (s <= mid) { mxto(res, qmx(s, e, lc, lo, mid)); } if (e > mid) { mxto(res, qmx(s, e, rc, mid + 1, hi)); } return res; } int ans; void solve(int l, int r, int big = 0) { if (l > r) { return; } ll sm = qsm(l, r); ii mx = qmx(l, r); //cerr << l << ' ' << r << ' ' << sm << ' ' << mx.FI << ' ' << mx.SE << '\n'; if (sm < big) { return; } ans++; solve(l, mx.SE - 1, mx.FI); solve(mx.SE + 1, r, mx.FI); } int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n; REP (i, 1, n + 1) { cin >> a[i]; upd(i, a[i]); } cin >> q; while (q--) { int t; cin >> t; if (t == 1) { int x, y; cin >> x >> y; upd(x, y); a[x] = y; } else { int l, r; cin >> l >> r; ans = 0; solve(l, r); cout << ans << '\n'; } } return 0; }

Compilation message (stderr)

fish2.cpp: In function 'void upd(int, int, int, int, int)':
fish2.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:53:5: note: in expansion of macro 'MLR'
   53 |     MLR;
      |     ^~~
fish2.cpp: In function 'll qsm(int, int, int, int, int)':
fish2.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:66:5: note: in expansion of macro 'MLR'
   66 |     MLR;
      |     ^~~
fish2.cpp: In function 'ii qmx(int, int, int, int, int)':
fish2.cpp:46:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
fish2.cpp:80:5: note: in expansion of macro 'MLR'
   80 |     MLR;
      |     ^~~
#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...