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 god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9
using namespace std;
typedef long long ll;
int n, ans = 1, v[1000002];
multiset<int> s;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> v[i];
s.insert(v[1]);
int i = 2;
while(i <= n && v[i] >= v[i-1])
s.insert(v[i]), ++i;
for(; i <= n; )
{
++ans;
multiset<int> ::iterator it = s.lower_bound(v[i]);
multiset<int> ::iterator it2 = it;
if(it == s.end())
{
int j = i+1;
s.insert(v[i]);
while(j <= n && v[j] >= v[j-1])
s.insert(v[j]), ++j;
i = j;
}
else
{
if(it == s.begin() && v[i] < *it)
{
int j = i+1;
int val = *it;
s.insert(v[i]);
while(j <= n && v[j] >= v[j-1] && v[j] <= val)
s.insert(v[j]), ++j;
i = j;
}
else
{
if(*it == v[i])
{
++it2;
if(it2 == s.end())
{
int j = i+1;
s.insert(v[i]);
while(j <= n && v[j] >= v[j-1])
s.insert(v[j]), ++j;
i = j;
}
else
{
int j = i+1;
int val = *it2;
s.insert(v[i]);
while(j <= n && v[j] >= v[j-1] && v[j] <= val)
s.insert(v[j]), ++j;
i = j;
}
}
else
{
int j = i+1;
int val = *it;
s.insert(v[i]);
while(j <= n && v[j] >= v[j-1] && v[j] <= val)
s.insert(v[j]), ++j;
i = j;
}
}
}
}
cout << ans;
return 0;
}
# | 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... |