oj.uz

Submission #260157

# Submission time Handle Problem Language Result Execution time Memory
260157 2020-08-09T11:58:48 Z sckmd Baloni (COCI15_baloni) C++14
100 / 100
 1410 ms 45720 KB 
#include <bits/stdc++.h>

using namespace std;
#define MAXN 1000005
typedef pair<int,int> pii;
set <pii> st;

void go(int height,int prev)
{
  if(st.lower_bound({height,prev})==st.end())return ;
  auto it = st.lower_bound({height,prev});
  pii x = *it;
  if(x.first != height)return ;
  if(x.second < prev)return ;
  st.erase(it);
  go(height-1,x.second);
}

int solve()
{
  int ans = 0;
  for(int height = MAXN-1; height > 0;)
  {
    if(st.lower_bound({height,-1})==st.end()){height--;continue;}
    /*auto it = st.lower_bound({height,-1});
    pii x = *it;
    if(x.first != height){height--;continue;}*/
    go(height,-1);
    ans++;
  }
  return ans;
}

int main()
{
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)
  {
    int h;
    cin >> h;
    st.insert({h,i});
  }
  cout << solve();
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 384 KB Output is correct
2 Correct 13 ms 384 KB Output is correct
3 Correct 17 ms 512 KB Output is correct
4 Correct 15 ms 640 KB Output is correct
5 Correct 1219 ms 41208 KB Output is correct
6 Correct 1410 ms 45720 KB Output is correct
7 Correct 1112 ms 37752 KB Output is correct
8 Correct 1105 ms 37116 KB Output is correct
9 Correct 1188 ms 39544 KB Output is correct
10 Correct 1300 ms 41080 KB Output is correct