Submission #900641

#TimeUsernameProblemLanguageResultExecution timeMemory
900641LucaIlieFish 2 (JOI22_fish2)C++17
0 / 100
2834 ms3136 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]; bool baul[MAX_N + 1], baur[MAX_N + 1]; long long s[MAX_N + 1]; int main() { int n; cin >> n; for ( int i = 1; i <= n; i++ ) { cin >> v[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; } for ( int i = 1; i < n; i++ ) { if ( leftt[i] == 0 ) baul[i] = 0; else baul[i] = (rightt[leftt[i]] <= i); } for ( int i = 2; i <= n; i++ ) { if ( rightt[i] == n + 1 ) baur[i] = 0; else baur[i] = (leftt[rightt[i]] >= i); } int ans = 0; for ( int i = 1; i <= n; i++ ) { int p; p = i; while ( p >= 2 && (rightt[p] <= i || baur[p]) ) p--; if ( p != 1 ) continue; p = n; while ( p <= n - 1 && (leftt[p] >= i || baul[p]) ) p++; if ( p == n ) ans++; } cout << ans; 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...