oj.uz

Submission #81164

# Submission time Handle Problem Language Result Execution time Memory
81164 2018-10-24T03:09:27 Z FutymyClone Baloni (COCI15_baloni) C++14
100 / 100
 1441 ms 93528 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int n, a[N], ans = 0;
set <int> pos[N];
bool used[N];

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]].insert(i);
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        ans++;
        int pt = a[i], lst = i;
        while (pt >= 1) {
            auto it = pos[pt].lower_bound(lst);
            if (it == pos[pt].end()) break;
            lst = *it;
            pos[pt].erase(it);
            used[lst] = true;
            pt--;
        }
    }

    printf("%d", ans);
    return 0;
}

Compilation message

baloni.cpp: In function 'int main()':
baloni.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
baloni.cpp:13:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]].insert(i);
                                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47484 KB Output is correct
2 Correct 45 ms 47568 KB Output is correct
3 Correct 44 ms 47568 KB Output is correct
4 Correct 46 ms 47860 KB Output is correct
5 Correct 1285 ms 88596 KB Output is correct
6 Correct 1441 ms 93528 KB Output is correct
7 Correct 1158 ms 93528 KB Output is correct
8 Correct 1137 ms 93528 KB Output is correct
9 Correct 1198 ms 93528 KB Output is correct
10 Correct 1232 ms 93528 KB Output is correct