Submission #339441

#TimeUsernameProblemLanguageResultExecution timeMemory
339441Dilshod_ImomovMoney (IZhO17_money)C++17
100 / 100
1012 ms48108 KiB
# include <bits/stdc++.h> # define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) # define int long long # define fi first # define se second using namespace std; const int N = 2e6 + 7; const int mod = 1e9 + 7; int a[N], t[4 * N], lz[4 * N]; void push( int v ) { lz[v * 2] += lz[v]; lz[v * 2 + 1] += lz[v]; t[v * 2] += lz[v]; t[v * 2 + 1] += lz[v]; lz[v] = 0; } void upd( int v, int l, int r, int pos ) { if ( l == r ) { t[v] ++; lz[v] ++; return; } int m = (l + r) / 2; push(v); if ( pos <= m ) { upd( v * 2, l, m, pos ); } else { upd( v * 2 + 1, m + 1, r, pos ); } t[v] = t[v * 2] + t[v * 2 + 1]; } int get( int v, int l, int r, int tl, int tr ) { if ( tl > tr ) { return 0; } if ( l == tl && tr == r ) { return t[v]; } push(v); int m = (l + r) / 2; int sum = get( v * 2, l, m, tl, min( m, tr ) ); sum += get( v * 2 + 1, m + 1, r, max( tl, m + 1 ), tr ); return sum; } int32_t main() { speed; int n; cin >> n; for ( int i = 1; i <= n; i++ ) { cin >> a[i]; } int ans = 0; for ( int i = 1; i <= n; i++ ) { int l = i, r = i; while ( a[r + 1] >= a[r] && get( 1, 1, N - 1, a[l] + 1, a[r + 1] - 1 ) == 0 ) { r++; } while ( l <= r ) { upd( 1, 1, N - 1, a[l++] ); } i = r; ans++; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...