Submission #870402

#	Time	Username	Problem	Language	Result	Execution time	Memory
870402		MercubytheFirst	Baloni (COCI15_baloni)	C++17	100 / 100	802 ms	96092 KiB

baloni

#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<map>
#include<set>
#include<climits>
#include<numeric>
#include<queue>
#include<unordered_map>
#include<string>
#include<climits>
#include<unordered_set>
#include<bitset>
#include<cstring>
#include<cmath>
#include<stack>
#include<tuple>
#include<complex>
#if 1
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define CDIV(a,b) (((a)+(b)-(1))/(b))
using namespace std;
using ll = long long;
using ld = long double;
const int inf = 10;
const ll mod = 998244353;
const ll N = 1e6+4;
const ld PI = acos((ld)-1);
#endif



void fileio(string s = "test"){
    #ifndef ONLINE_JUDGE
        freopen((s+string(".in")).c_str(),"r",stdin);
        freopen((s+string(".out")).c_str(),"w",stdout);
    #endif
}

ll bpow(ll a, ll p)
{
    if(a == 0 or a == 1)return a;
    ll ans = 1;
    while(p)
    {
        if(p&1)ans = ans * a % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return ans;
}

ll add(ll a, ll b){
    if(a + b >= mod) 
        return a + b - mod;
    return a + b;
}

ll sub(ll a, ll b){
    if(a - b >= 0)
        return a - b;
    return a - b + mod;
}



ll mul(ll a, ll b){
    return (a%mod)*(b%mod)%mod;
}


inline void solve()
{
    int n;
    cin >> n;
    set<int> keep[N];
    vector<int> v(n + 1, -1);
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        keep[v[i]].insert(i);
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i){
        if(v[i] == -1)
            continue;
        ans++;
        // cout << i << ' ';
        int cur = v[i], lasti = i;
        while(cur >= 1 and !keep[cur].empty()){
            auto it = keep[cur].lower_bound(lasti);
            if(it == keep[cur].end())
                break;
            v[*it] = -1;
            lasti = *it;
            keep[cur].erase(it);
            cur--;
        }
    }
    cout << ans << endl;

}

signed main(){
    // fileio();
    fio; 
    //int t;cin >> t;while(t-->0)
        solve();

}


/*

*/

Compilation message (stderr)

baloni.cpp: In function 'void fileio(std::string)':
baloni.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((s+string(".in")).c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
baloni.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((s+string(".out")).c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100