Submission #1240002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240002		asdfghqwert	Baloni (COCI15_baloni)	C++20	40 / 100	2099 ms	95832 KiB

baloni

//#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC optimize("O3,Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define int long long int
typedef long long ll;
using namespace std;


int32_t main() {
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    int n , ans = 0;cin >> n;
    vector<set<int>> a(1'000'001);
    vector<int> arr(n + 1);
    for(int i = 1 ; i <= n ;i++){cin >> arr[i];a[arr[i]].insert(i);}
    vector<bool> dead(n + 1);
    for(int i = 1 ; i <= n ; i++){
        if(dead[i])continue;
        int cur = i , val = arr[i];
        ans++;
        while(true){
            auto it = lower_bound(a[val].begin() , a[val].end() , cur);
            if(it == a[val].end())break;
            cur = *it;
            dead[cur] = 1;
            a[val].erase(cur);
            val--;
        }
    }
    cout << ans;
}

• Subtask 1: 40 / 100