oj.uz

답안 #270599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
270599 2020-08-17T19:40:26 Z wutwere Baloni (COCI15_baloni) C++17
100 / 100
 1171 ms 92540 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define _F(i,a,b,s) for(int i=(a);((s)>0?i<(b):i>(b));i+=(s))
#define _1(e) _F(i,0,e,1)
#define _2(i,e) _F(i,0,e,1)
#define _3(i,b,e) _F(i,b,e,(b)<(e)?1:-1)
#define _G(a,b,c,d,e,...) e
#define FOR(...) _G(__VA_ARGS__,_F,_3,_2,_1)(__VA_ARGS__)

const int MAXN = 1e6 + 1;

set<int> pos[MAXN];

int main() {
	ios::sync_with_stdio(0),cin.tie(0);
	int n; cin >> n;
	set<int> hv;
	FOR (i, n) {
		int h; cin >> h;
		pos[h].insert(i);
		hv.insert(h);
	}
	int ans = 0;
	for (auto it = hv.rbegin(); it != hv.rend(); it++) {
		int i = *it;
		while (!pos[i].empty()) {
			ans++;
			auto lastit = pos[i].begin();
			int last = *lastit;
			pos[i].erase(lastit);
			FOR (j, i - 1, 0) {
				auto nxtit = pos[j].upper_bound(last);
				if (nxtit != pos[j].end()) {
					last = *nxtit;
					pos[j].erase(nxtit);
				} else {
					break;
				}
			}
		}
	}
	cout << ans << '\n';
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 47360 KB Output is correct
2 Correct 29 ms 47488 KB Output is correct
3 Correct 32 ms 47480 KB Output is correct
4 Correct 31 ms 47616 KB Output is correct
5 Correct 986 ms 88188 KB Output is correct
6 Correct 1171 ms 92540 KB Output is correct
7 Correct 949 ms 84472 KB Output is correct
8 Correct 928 ms 84088 KB Output is correct
9 Correct 957 ms 86392 KB Output is correct
10 Correct 1006 ms 87788 KB Output is correct