oj.uz

Submission #268536

# Submission time Handle Problem Language Result Execution time Memory
268536 2020-08-16T12:38:47 Z mayhoubsaleh Baloni (COCI15_baloni) C++14
100 / 100
 1514 ms 100412 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;
const ll maxn=1e6+100;
const ll inf=1e9+10;

ll n;
ll h[maxn];
int ans;
bool don[maxn];
set<int>pos[maxn];

void arr(int cur,int id){
    if(!cur)return;
    auto it=pos[cur].lower_bound(id);
    if(it==pos[cur].end())return;
    int x=*it;
    don[x]=1;
    pos[cur].erase(it);
    arr(cur-1,x);
}
int main()
{
    IOS
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>h[i];
        pos[h[i]].insert(i);
    }

    for(int i=0;i<n;i++){
        if(don[i])continue;
        arr(h[i],i);
        ans++;
    }

    cout<<ans<<endl;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47360 KB Output is correct
2 Correct 36 ms 47488 KB Output is correct
3 Correct 35 ms 47616 KB Output is correct
4 Correct 35 ms 47608 KB Output is correct
5 Correct 1204 ms 95096 KB Output is correct
6 Correct 1514 ms 100412 KB Output is correct
7 Correct 1078 ms 91132 KB Output is correct
8 Correct 1036 ms 90608 KB Output is correct
9 Correct 1189 ms 93116 KB Output is correct
10 Correct 1324 ms 94712 KB Output is correct