oj.uz

Submission #449463

# Submission time Handle Problem Language Result Execution time Memory
449463 2021-08-02T06:29:49 Z dz001 Baloni (COCI15_baloni) C++11
100 / 100
 1283 ms 95908 KB 
/* 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47308 KB Output is correct
2 Correct 28 ms 47296 KB Output is correct
3 Correct 26 ms 47444 KB Output is correct
4 Correct 27 ms 47656 KB Output is correct
5 Correct 1220 ms 91220 KB Output is correct
6 Correct 1283 ms 95908 KB Output is correct
7 Correct 974 ms 87328 KB Output is correct
8 Correct 986 ms 86824 KB Output is correct
9 Correct 1126 ms 89296 KB Output is correct
10 Correct 1175 ms 90760 KB Output is correct