Submission #1078047

#TimeUsernameProblemLanguageResultExecution timeMemory
10780470npataFish 2 (JOI22_fish2)C++17
0 / 100
0 ms348 KiB
#include<bits/stdc++.h> using namespace std; #define vec vector #define int long long const int INF = 1e17; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vec<int> A(N); set<pair<int, int>> A_s; for(int i = 0; i<N; i++) { cin >> A[i]; A_s.insert({-A[i], i}); } int Q; cin >> Q; while(Q--) { //cerr << "f" << '\n'; int T; cin >> T; int X, Y; cin >> X >> Y; X--; A_s.erase({-A[X], X}); A[X] = Y; A_s.insert({-Y, X}); vec<int> l(N); vec<int> r(N); vec<pair<int, int>> hi{{INF, -1}}; for(int i = 0; i<N; i++) { while(hi.back().first <= A[i]) { hi.pop_back(); //cerr << "here1" << '\n'; } l[i] = hi.back().second; hi.push_back({A[i], i}); } vec<pair<int, int>> hi_r{{INF, N}}; for(int i = N-1; i>=0; i--) { while(hi_r.back().first < A[i]) { //cerr << "here2" << '\n'; hi_r.pop_back(); } r[i] = hi_r.back().second; hi_r.push_back({A[i], i}); } vec<bool> valid(N); vec<int> prefixsums(N+2); for(int i = 1; i<=N; i++) { prefixsums[i] = prefixsums[i-1] + A[i-1]; } prefixsums[N+1] = prefixsums[N]; valid[(*A_s.rbegin()).second] = true; int ans = 1; for(auto [_, i] : A_s) { int cl = l[i]; int cr = r[i]; int sum = prefixsums[cr+1]-prefixsums[cl+1]; if(cl != -1) { if(sum >= A[cl]) valid[i] = valid[i] | valid[cl]; } if(cr != N) { if(sum >= A[cr]) valid[i] = valid[i] | valid[cr]; } ans += valid[i]; } cout << ans << '\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...