Submission #449463

#	Time	Username	Problem	Language	Result	Execution time	Memory
449463		dz001	Baloni (COCI15_baloni)	C++11	100 / 100	1283 ms	95908 KiB

baloni

/* ldmm is n00b */
#include <bits/stdc++.h>

using namespace std;

#define Cerr cerr << "\nTest: "
#define endl "\n"
#define fi first
#define se second
#define pb push_back

#ifdef RICARDO
    #define bug(x) cerr << #x << " = " << (x) << endl;
    #define block if(1)
#else
    #define bug(x) "IDINGO"
    #define block if(0)
#endif


template<class T> bool mini(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool maxi(T &a, T b) { return a < b ? (a = b, true) : false; }

typedef pair<int, int> pii;
typedef long long ll;
typedef double ld;

const int N=1e6+10;
set<int> s[N];
int a[N];
int n;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL
    freopen("i", "r", stdin);
    freopen("o", "w", stdout);
#endif

    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i],s[a[i]].insert(i);

    int ans=0;
    for(int i=0;i<n;++i){
        if(!s[a[i]].count(i))continue;
        ++ans;
        int cur=i;
        while(1){
            auto it=s[a[cur]-1].upper_bound(cur);
            if(it==s[a[cur]-1].end())break;
            s[a[cur]-1].erase(it);
            cur=*it;
        }
    }
    cout<<ans;

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

• Subtask 1: 100 / 100