Submission #1024860

#TimeUsernameProblemLanguageResultExecution timeMemory
1024860UnforgettableplFish 2 (JOI22_fish2)C++17
25 / 100
4090 ms5320 KiB
// #pragma GCC optimize("Ofast","unroll-loops") #include <bits/stdc++.h> using namespace std; // #define int long long const int INF = INT32_MAX; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> arr(n+1); for(int i=1;i<=n;i++)cin>>arr[i]; vector<pair<int,int>> connection(n+1); vector<int> left(n+1),right(n+1); vector<long long> pref(n+2); vector<pair<int,int>> adj(n+1); auto solve = [&](int l,int r){ pref[l-1]=0; for(int i=l;i<=r;i++){ pref[i]=pref[i-1]+arr[i]; adj[i].first=adj[i].second=0; } stack<pair<int,int>> s; s.emplace(INF,l-1); for(int i=l;i<=r;i++){ while(s.top().first<=arr[i])s.pop(); connection[i]=s.top(); left[i]=s.top().second; s.emplace(arr[i],i); } while(!s.empty())s.pop(); s.emplace(INF,r+1); for(int i=r;i>=l;i--){ while(s.top().first<arr[i])s.pop(); connection[i]=min(s.top(),connection[i]); right[i]=s.top().second; s.emplace(arr[i],i); } for(int i=l;i<=r;i++){ if(connection[i].second<i)adj[connection[i].second].second=i; else adj[connection[i].second].first=i; } int ans = 0; function<void(int,int)> dfs = [&](int x,int threshold){ if(pref[right[x]-1]-pref[left[x]]<threshold)return; ans++; if(adj[x].first)dfs(adj[x].first,arr[x]); if(adj[x].second)dfs(adj[x].second,arr[x]); }; dfs(adj[l-1].second,0); return ans; }; int q; cin >> q; for(int i=1;i<=q;i++){ int type;cin>>type; if(type==1){ int x,y;cin>>x>>y; arr[x]=y; } else { int l,r;cin>>l>>r; cout << solve(l,r) << '\n'; } } }
#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...