Submission #832163

#TimeUsernameProblemLanguageResultExecution timeMemory
832163Magikarp4000Fish 2 (JOI22_fish2)C++17
25 / 100
4058 ms5404 KiB
#include <bits/stdc++.h> using namespace std; #define OPTM ios_base::sync_with_stdio(0); cin.tie(0); #define INF int(1e9+7) #define ln '\n' #define ll long long #define ull unsigned long long #define ui unsigned int #define us unsigned short #define FOR(i,s,n) for (int i = s; i < n; i++) #define FORR(i,n,s) for (int i = n; i > s; i--) #define FORX(u, arr) for (auto u : arr) #define PB push_back #define F first #define S second #define PII pair<int, int> #define PLL pair<ll, ll> #define UM unordered_map #define US unordered_set #define PQ priority_queue #define ALL(v) v.begin(), v.end() const ll LLINF = 1e18+1; #define int long long const int MAXN = 1e5+5; int n,q; int a[MAXN]; int calc(int l, int r) { stack<pair<int,PII>> st; vector<PII> v; FOR(i,l,r+1) { int cur = a[i], cursta = i; while (!st.empty() && cur >= a[st.top().S.S]) { int val = st.top().F, sta = st.top().S.F, en = st.top().S.S; // cout << i << ": " << val << " " << sta << " " << en << ln; st.pop(); cur += val; cursta = sta; if ((sta == l || a[sta-1] > cur-a[i]) && a[i] > cur-a[i]) v.PB({sta,i-1}); } st.push({cur,{cursta,i}}); } int cur = LLINF; while (!st.empty() && cur >= a[st.top().S.S]) { int val = st.top().F, sta = st.top().S.F, en = st.top().S.S; // cout << val << " " << sta << " " << en << ln; st.pop(); cur += val; if ((sta == l || a[sta-1] > cur-LLINF)) v.PB({sta,r}); } // FORX(u,v) cout << u.F << " " << u.S << ln; // return 0; stack<PII> st1; int j = v.size()-1; int cnt = 0; FORR(i,n-1,-1) { while (!st1.empty() && st1.top().F == i) st1.pop(); while (j >= 0 && v[j].S == i) st1.push({v[j].F-1,j}), j--; if (!st1.empty() && v[st1.top().S] == make_pair(l,r)) cnt++; } return cnt; } signed main() { OPTM; cin >> n; FOR(i,0,n) cin >> a[i]; a[n] = LLINF; cin >> q; FOR(_,0,q) { int t; cin >> t; if (t == 1) { int x,y; cin >> x >> y; a[x-1] = y; } else { int l,r; cin >> l >> r; l--; r--; cout << calc(l,r) << ln; } } }

Compilation message (stderr)

fish2.cpp: In function 'long long int calc(long long int, long long int)':
fish2.cpp:35:55: warning: unused variable 'en' [-Wunused-variable]
   35 |             int val = st.top().F, sta = st.top().S.F, en = st.top().S.S;
      |                                                       ^~
fish2.cpp:46:51: warning: unused variable 'en' [-Wunused-variable]
   46 |         int val = st.top().F, sta = st.top().S.F, en = st.top().S.S;
      |                                                   ^~
#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...