#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define radhey krishna
#define endl "\n"
const int N = 1e6;
#define MOD 1000000007
// bool sortbysec(const pair<int,int> &a,
// const pair<int,int> &b)
// {
// return (a.second < b.second);
// }
ll gcd(ll a, ll b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// void printDivisors(int n)
// {
// // Note that this loop runs till square root
// for (int i=1; i<=sqrt(n); i++)
// {
// if (n%i == 0)
// {
// // If divisors are equal, print only one
// if (n/i == i)
// printf("%d ", i);
// else // Otherwise print both
// printf("%d %d ", i, n/i);
// }
// }
// }
// void SieveOfEratosthenes(int n)
// {
// bool prime[n + 1];
// memset(prime, true, sizeof(prime));
// for (int p = 2; p * p <= n; p++)
// {
// if (prime[p] == true)
// {
// for (ll i = p * p; i <= n; i += p)
// prime[i] = false;
// }
// }
// for (ll p = 2; p <= n; p++){
// if (prime[p]){
// cout << p << " ";
// //ans += prime[p];
// }
// }
// cout<<endl;
// // return ans;
// }
// std::vector<int> v;
// void primeFactors(int n)
// {
// while (n % 2 == 0)
// {
// // cout << 2 << " ";
// v.push_back(2);
// n = n/2;
// }
// for (int i = 3; i <= sqrt(n); i = i + 2)
// {
// while (n % i == 0)
// {
// //cout << i << " ";
// v.push_back(i);
// n = n/i;
// }
// }
// if (n > 2)
// //cout << n << " ";
// v.push_back(n);
// }
int ceil(int x,int y)
{
if(x%y)
{
int f=(x/y);
return f+1;
}
else
{
return (x/y);
}
}
ll poww(ll a ,ll b){
ll res = 1;
for(int i = 1; i <= b; i++){
res *= a;
}
return res;
}
ll SUM(ll x){
ll sum = 0;
while(x){
sum += x%10;
x = x/10;
}
return sum;
}
ll fast_exp(int base, int exp) {
ll res=1;
while(exp>0) {
if(exp%2==1) res=(res*base)%MOD;
base=(base*base)%MOD;
exp/=2;
}
return res%MOD;
}
int no_of_operations(string str, int n)
{
int count = 0;
for (int i = 0; i < n - 1; i++) {
if (str[i] != str[i + 1])
count++;
}
return (count + 1) / 2;
}
void solve(){
int n;
cin>>n;
stack<int>st;
st.push(0);
int a[n+1];
for(int i = 0; i < n; i++){
cin>>a[i];
}
int cnt = 0;
for(int i = 0; i < n ;i++){
while(!st.empty() && st.top() > a[i]){
st.pop();
}
if(st.top() == a[i]){
continue;
}
if(st.top() < a[i]){
st.push(a[i]);
cnt++;
}
}
cout<<cnt<<endl;
}
int main(){
/*
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input.txt", "r", stdin);
// for writing output to output.txt
freopen("output.txt", "w", stdout);
#endif
*/
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int t =1;
//cin>>t;
while(t--){
//cout<<"Case #"<<i<<": ";
solve();
//i++;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
5 ms |
492 KB |
Output is correct |
| 5 |
Correct |
7 ms |
620 KB |
Output is correct |
| 6 |
Correct |
12 ms |
876 KB |
Output is correct |
| 7 |
Correct |
12 ms |
748 KB |
Output is correct |
