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 fs first
#define ss second
#define endl '\n'
#define all(a) a.begin(), a.end()
#define print(a) \
for (auto x : a) \
cout << x << ' '; \
cout << endl;
#define printmp(a) \
for (auto x : a) \
cout << x.fs << ' ' << x.ss << endl;
struct SegTree {
int size = 1;
vector<int> sums;
SegTree (){
while(1e6 > size)
size <<= 1;
sums.resize(size << 1);
}
void add(int i, int x, int lx, int rx){
if(rx == lx + 1){
sums[x] ++;
return;
}
int m = (lx + rx) >> 1;
if(i < m)
add(i, (x << 1) + 1, lx, m);
else
add(i, (x << 1) + 2, m, rx);
sums[x] = sums[(x << 1) + 1] + sums[(x << 1) + 2];
}
void add(int i){
add(i, 0, 0, size);
}
int sum(int l, int r, int x, int lx, int rx){
if(l <= lx and rx <= r)
return sums[x];
if(r <= lx or rx <= l)
return 0;
int m = (lx + rx) >> 1;
return sum(l, r, (x << 1) + 1, lx, m) + sum(l, r, (x << 1) + 2, m, rx);
}
int sum(int l, int r){
return sum(l, r, 0, 0, size);
}
};
void solve()
{
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i ++)
cin >> a[i];
SegTree s;
int ans = 0;
int l = 0, r = 0;
while(l < n and r < n){
while(r < n and a[max(l, r - 1)] <= a[r] and s.sum(a[l] + 1, a[r]) == 0)
r ++;
for(int i = l; i < r; i ++)
s.add(a[i]);
ans ++;
l = r;
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
cout << endl;
}
}
# | 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... |