Submission #1276211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276211		duyanhchupapi	Baloni (COCI15_baloni)	C++20	100 / 100	412 ms	96828 KiB

baloni

#include <bits/stdc++.h>
using namespace std; using ll = long long; const int N = 1e6 + 5;
int n, h[N], nxt[N];
set <int> luu[N]; 
bool vis[N];
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen("baloni.inp", "r", stdin);
	//freopen("baloni.out", "w", stdout);
	cin >> n;
	for(int i=1;i<=n;++i) cin >> h[i], luu[h[i]].insert(i);
	
	for(int i=1;i<=n;++i) {
		int j = h[i] - 1;
		if(luu[j].empty() || *luu[j].rbegin() < i) continue;
		auto it = luu[j].lower_bound(i); 
		nxt[i] = *it;
		luu[j].erase(it);
	}
	
	int ans = 0;
	for(int i=1;i<=n;++i) {
		if(vis[i]) continue;
		ans++;
		int cur = i;
		while(1) {
			vis[cur] = 1;
			cur = nxt[cur];
			if(cur == 0) break;
		}
	}
	cout << ans;
	return 0;
}

• Subtask 1: 100 / 100