oj.uz

Submission #708011

# Submission time Handle Problem Language Result Execution time Memory
708011 2023-03-10T18:53:36 Z TAhmed33 Baloni (COCI15_baloni) C++
100 / 100
 273 ms 11852 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 960 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 192 ms 11576 KB Output is correct
6 Correct 273 ms 11852 KB Output is correct
7 Correct 194 ms 9528 KB Output is correct
8 Correct 198 ms 9420 KB Output is correct
9 Correct 192 ms 10564 KB Output is correct
10 Correct 231 ms 10456 KB Output is correct