oj.uz

Submission #237340

# Submission time Handle Problem Language Result Execution time Memory
237340 2020-06-06T03:12:15 Z aloo123 Baloni (COCI15_baloni) C++14
100 / 100
 1174 ms 96936 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define f first
#define s second
#define pr(x) cout<<x<<endl;
#define pr2(x,y) cout<<x<<" "<<y<<endl;
#define pr3(x,y,z) cout<<x<<" "<<y<<endl;
#define prv(v) for(auto x:v) cout<<x<<" ";
#define ffs fflush(stdout);
#define int ll
#define sz(x) (ll)x.size()
using namespace std;
 
 
const ll MOD = 1e9+7;
const ll INF = LLONG_MAX;
const ll LOG = 29;
#define PI 3.141592653589793238 
 
 
 


const ll N =(1e6+5);

ll fact[N];

long long binpow(long long a, long long b) {
     a%=MOD;    
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%MOD;
        a = (a * a)%MOD;
 
        
        b >>= 1;
    }
     res%=MOD;
    return res;
}
void ini(){
    fact[0] = 1;
    for(int i = 1;i < N;i++){
        fact[i] = (fact[i-1] * i)%MOD;
    }
}
ll ncr(ll n,ll r){
    ll ret = fact[n];
    ret = (ret * binpow(fact[r],MOD-2))%MOD;
    ret = (ret * binpow(fact[n-r],MOD-2))%MOD;
    return ret;
}
ll n;
ll a[N];
bool vis[N];
set<ll> idx[N];
void solve(){
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        idx[a[i]].in(i);
    }
    ll ans =0;
    for(int i = 1;i <= n;i++){
        if(vis[i]) continue;
        ans++;
        ll h = a[i];
        ll pre = i;
        while(true){
            if(h <= 0) break;
            if(idx[h].empty()) break;
            auto it = idx[h].lower_bound(pre);
            if(it == idx[h].end())
                break;
            vis[*it]= true;
            idx[h].erase(it);
            pre = *it;
            h--;
        }

    }
    cout << ans << endl;
}       

 
signed main(){
    ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
    
       
 
     ll tt=1;   
    // cin >> tt;
    while(tt--){
        solve();
    }    
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47360 KB Output is correct
2 Correct 33 ms 47488 KB Output is correct
3 Correct 33 ms 47488 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 1052 ms 91492 KB Output is correct
6 Correct 1174 ms 96936 KB Output is correct
7 Correct 934 ms 88312 KB Output is correct
8 Correct 937 ms 87940 KB Output is correct
9 Correct 1083 ms 89976 KB Output is correct
10 Correct 1069 ms 91664 KB Output is correct