Submission #237340

#TimeUsernameProblemLanguageResultExecution timeMemory
237340aloo123Baloni (COCI15_baloni)C++14
100 / 100
1174 ms96936 KiB
#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(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...