Submission #708011

#	Time	Username	Problem	Language	Result	Execution time	Memory
708011		TAhmed33	Baloni (COCI15_baloni)	C++98	100 / 100	273 ms	11852 KiB

baloni

#include <bits/stdc++.h>
using namespace std;
int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n;
	cin >> n;
	int arr[n + 1] = {0};
	unordered_map<int, deque<int>> pos;
	int mx = 0;
	int mn = 1e9;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		mx = max(mx, arr[i]);
		mn = min(mn, arr[i]);
		pos[arr[i]].push_back(i);
	}
	int ans = 0;
	while (mx >= mn) {
		if (pos[mx].size() == 0) {
			mx--;
			continue;
		}
		int arrow = mx;
		int cur = pos[mx].front();
		arrow--;
		pos[mx].pop_front();
		while (arrow != 0) {
			if (pos[arrow].size() == 0) break;
			int ub = upper_bound(pos[arrow].begin(), pos[arrow].end(), cur) - pos[arrow].begin();
			if (ub == pos[arrow].size()) {
				break;
			}
			cur = pos[arrow][ub];
			pos[arrow].erase(pos[arrow].begin() + ub);
			arrow--;
		}
		ans++;
	}
	cout << ans << endl;
}

Compilation message (stderr)

baloni.cpp: In function 'int main()':
baloni.cpp:32:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    if (ub == pos[arrow].size()) {
      |        ~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100