This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
void printVector(vector<int> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
struct Fenwick{
int N;
vector<int> tree;
Fenwick(int n){
this->N = n;
tree.resize(N+1);
}
int sum(int k) {
int s = 0;
while (k >= 1) {
s += tree[k];
k -= k&-k;
}
return s;
}
void add(int k, int x = 1) {
while (k <= N) {
tree[k] += x;
k += k&-k;
}
}
int query(int l, int r){
if (r < l) return 0;
int ans = sum(r);
if (l > 1) ans -= sum(l-1);
return ans;
}
};
void solve(){
Fenwick bit(1000001);
int n; cin >> n;
vector<int> a(n+1);
FOR(i,1,n+1) cin >> a[i];
int c = 1;
int ans = 0;
FOR(i,1,n+1){
if (a[i] >= a[i-1]){
if (bit.query(a[c]+1, a[i]-1)){
FOR(j,c,i){
bit.add(a[j]);
}
ans++;
c = i;
}
}else{
FOR(j,c,i){
bit.add(a[j]);
}
ans++;
c = i;
}
// cout << ans << " ";
}
// cout << endl;
cout << ans+1 << endl;
}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int t = 1; // cin >> t;
while (t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |