oj.uz

답안 #559275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559275 2022-05-09T14:55:06 Z nguyen31hoang08minh2003 Baloni (COCI15_baloni) C++14
100 / 100
 1052 ms 97420 KB 
/*
\/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \  M M 9 2 / /  \ \/ /  \ \/ /
  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \ o a t 0  / /\ \  / /\ \  / /\
\/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \  n y h 2 / /  \ \/ /  \ \/ /
  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \ d        / /\ \  / /\ \  / /\
  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ / a  \/ /  \ \/ /  \ \/ /  \ \/
/\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  /  y \  / /\ \  / /\ \  / /\ \
  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /    \/ /  \ \/ /  \ \/ /  \ \/
/\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \  / /\ \
*/
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) int((x).size())
#define FOR(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define long long long

template<class A, class B>
bool minimize(A &a, const B& b) {
    return a <= b ? false : (a = b, true);
}

template<class A, class B>
bool maximize(A &a, const B& b) {
    return a >= b ? false : (a = b, true);
}

template<class X, class Y>
std::ostream& operator << (std::ostream& outputStream, const std::pair<X, Y> &p) {
    return outputStream << '{' << p.first << ", " << p.second >> '}';
}

template<class T>
std::ostream& operator << (std::ostream& outputStream, const std::vector<T>& values) {
    outputStream << '{';
    for (const T& value : values)
        outputStream << value << ' ';
    return outputStream << '}';
}

using namespace std;

const int MAX_N = 1e6 + 5;
#define MAX_H MAX_N

signed main() {
    set<int>::iterator b;
    int N, result = 0, H[MAX_N]{};
    set<int> p[MAX_H];
    bool seen[MAX_N]{};
//    freopen("input.INP", "r", stdin);
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
        p[H[i]].insert(i);
    }
    for (int i = 1, j, z; i <= N; ++i) {
        if (seen[i])
            continue;
        ++result;
        for (j = H[i], z = i; z <= N; --j) {
            b = p[j].lower_bound(z);
            if (b == p[j].end())
                break;
            z = *b;
            p[j].erase(b);
            seen[z++] = true;
        }
    }
    cout << result << '\n';
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 52172 KB Output is correct
2 Correct 35 ms 52180 KB Output is correct
3 Correct 34 ms 52272 KB Output is correct
4 Correct 37 ms 52296 KB Output is correct
5 Correct 1012 ms 92992 KB Output is correct
6 Correct 1029 ms 97420 KB Output is correct
7 Correct 807 ms 89368 KB Output is correct
8 Correct 883 ms 88780 KB Output is correct
9 Correct 1052 ms 91208 KB Output is correct
10 Correct 1022 ms 92556 KB Output is correct