oj.uz

답안 #237339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237339 2020-06-06T03:10:09 Z aloo123 Baloni (COCI15_baloni) C++14
0 / 100
 2000 ms 96888 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;
            auto it = idx[h].lower_bound(pre);
            if(it == idx[h].end())
                break;
            vis[*it]= true;
            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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 47352 KB Output isn't correct
2 Incorrect 31 ms 47488 KB Output isn't correct
3 Incorrect 34 ms 47488 KB Output isn't correct
4 Incorrect 34 ms 47616 KB Output isn't correct
5 Execution timed out 2074 ms 91384 KB Time limit exceeded
6 Execution timed out 2098 ms 96888 KB Time limit exceeded
7 Execution timed out 2085 ms 88056 KB Time limit exceeded
8 Execution timed out 2059 ms 87544 KB Time limit exceeded
9 Execution timed out 2104 ms 89848 KB Time limit exceeded
10 Execution timed out 2089 ms 91612 KB Time limit exceeded