Submission #603328

#TimeUsernameProblemLanguageResultExecution timeMemory
603328tamthegodMoney (IZhO17_money)C++14
0 / 100
25 ms8148 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, a[maxN]; int bit[maxN]; void update(int pos, int val) { while(pos < maxN) { bit[pos] += val; pos += (pos & (-pos)); } } int get(int pos) { int res = 0; while(pos) { res += bit[pos]; pos -= (pos & (-pos)); } return res; } void ReadInput() { cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; } void Solve() { for(int i=1; i<maxN; i++) update(i, 1); int res = 1; for(int i=1; i<=n; i++) { update(a[i], -1); if(a[i] < a[i - 1]) { res++; continue; } if(a[i] == a[i - 1]) continue; if(get(a[i] - 1) - get(a[i - 1]) != (a[i] - a[i - 1] - 1)) res++; } cout << res; } int32_t main() { // freopen("x.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...