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>
#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()
{
int res = 1;
vector<int> bin;
int last = a[1];
a[0] = a[1];
for(int i=1; i<=n; i++)
{
update(a[i], 1);
if(a[i] < a[i - 1])
{
res++;
for(int v : bin) update(v, 1);
bin.clear();
last = a[i];
continue;
}
if(i == 2)
{
//cout << last;return;
}
if(a[i] == a[i - 1]) continue;
if(get(a[i] - 1) - get(last))
{
res++;
for(int v : bin) update(v, 1);
bin.clear();
last = a[i];
}
}
cout << res;
}
int32_t main()
{
// freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
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... |