Submission #903846

#TimeUsernameProblemLanguageResultExecution timeMemory
903846LucaIlieFish 2 (JOI22_fish2)C++17
5 / 100
4006 ms3084 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5; int v[MAX_N + 1], leftt[MAX_N + 1], rightt[MAX_N + 1]; long long s[MAX_N + 1]; void init( int n ) { for ( int i = 1; i <= n; i++ ) s[i] = s[i - 1] + v[i]; for ( int i = 1; i < n; i++ ) { int l = 0, r = i + 1; while ( r - l > 1 ) { int mid = (l + r) / 2; if ( s[i] - s[mid - 1] >= v[i + 1] ) l = mid; else r = mid; } leftt[i] = l; } for ( int i = 2; i <= n; i++ ) { int l = i - 1, r = n + 1; while ( r - l > 1 ) { int mid = (l + r) / 2; if ( s[mid] - s[i - 1] >= v[i - 1] ) r = mid; else l = mid; } rightt[i] = r; } } int main() { int n; cin >> n; for ( int i = 1; i <= n; i++ ) cin >> v[i]; init( n ); int q; cin >> q; while ( q-- ) { int t, l, r; cin >> t >> l >> r; if ( t == 1 ) { v[l] = r; init( n ); continue; } int ans = 0; for ( int i = l; i <= r; i++ ) { int p; p = i; while ( p >= l + 1 && (rightt[p] <= i || (rightt[p] <= r && leftt[rightt[p] - 1] >= p)) ) p--; if ( p != l ) continue; p = i; while ( p <= r - 1 && (leftt[p] >= i || (leftt[p] >= l && rightt[leftt[p] + 1] <= p)) ) p++; if ( p == r ) ans++; } cout << ans << "\n"; } return 0; }
#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...