#include <bits/stdc++.h>
#define F first
#define S second
#define Pb push_back
using namespace std;
int n,a[1000006],fix[1000006],Ans,Ps;
pair < int , int > p [1000006];
vector < vector < pair < int , int > > > V;
vector < pair < int , int > > v,Z;
set < int > st;
void go(int x,int idx)
{
int ko=0,ID=idx;
Ans++;
fix[idx]=1;
for (int i=idx+1; i<=n; i++)
{
if (a[i]<x) break;
if (st.upper_bound(x)==st.end() || a[i]<=*st.upper_bound(x))
{
fix[i]=1;
ID=i;
x=a[i];
}
else break;
}
for (int i=idx; i<=ID; i++)
st.insert(a[i]);
}
main ()
{
ios::sync_with_stdio(false);
cin>>n;
for (int i=1; i<=n; i++)
cin>>a[i];
for (int i=1; i<=n; i++)
{
if (!fix[i]) go(a[i],i);
/*
for (int j=1; j<=n; j++)
cout<<fix[j]<<" ";
cout<<endl;*/
}
cout<<Ans<<endl;
}
/*
10
1 4 6 2 3 7 10 8 9 5
| 1 4 6 | 2 3 | 7 10 | 8 9 | 5 |
6
3 6 4 5 1 2
5
1 3 5 2 4
8
1 3 2 4 5 8 7 6
5
2 3 5 3 5
4
2 2 2 2
5
2 4 5 2 5
*/
Compilation message
money.cpp: In function 'void go(int, int)':
money.cpp:17:6: warning: unused variable 'ko' [-Wunused-variable]
int ko=0,ID=idx;
^~
money.cpp: At global scope:
money.cpp:39:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main ()
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
276 KB |
Output is correct |
| 4 |
Correct |
1 ms |
356 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
276 KB |
Output is correct |
| 4 |
Correct |
1 ms |
356 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
276 KB |
Output is correct |
| 4 |
Correct |
1 ms |
356 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
276 KB |
Output is correct |
| 4 |
Correct |
1 ms |
356 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
