Submission #137126

#TimeUsernameProblemLanguageResultExecution timeMemory
137126meatrowMoney (IZhO17_money)C++17
100 / 100
216 ms15012 KiB
#pragma GCC optimize("O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") //#pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 1e6 + 5; int f[N]; void add(int pos) { for (; pos < N; pos |= pos + 1) { f[pos]++; } } int get(int pos) { int res = 0; for (; pos >= 0; pos = (pos & (pos + 1)) - 1) { res += f[pos]; } return res; } int sum(int l, int r) { if (l > r) { return 0; } return get(r) - get(l - 1); } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int ans = 1; int i = 0; for (int j = 1; j < n; j++) { if (a[j] < a[j - 1] || sum(a[i] + 1, a[j] - 1)) { ans++; for (int k = i; k < j; k++) { add(a[k]); } i = j; } } 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...