Submission #559275

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
559275	2022-05-09T14:55:06 Z	nguyen31hoang08minh2003	Baloni (COCI15_baloni)	C++14	100 / 100	1052 ms	97420 KB

baloni

/*
\/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \ \/ /  \  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

#	Verdict	Execution time	Memory	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