Submission #268536

#	Time	Username	Problem	Language	Result	Execution time	Memory
268536		mayhoubsaleh	Baloni (COCI15_baloni)	C++14	100 / 100	1514 ms	100412 KiB

baloni

#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 / 100