oj.uz

Submission #516317

# Submission time Handle Problem Language Result Execution time Memory
516317 2022-01-21T05:20:15 Z Jomnoi Global Warming (NOI13_gw) C++17
23 / 40
 270 ms 22524 KB 
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 1e6 + 10;

int parent[N];
bool appeared[N];

int root(int u) {
    if(u == parent[u]) {
        return u;
    }
    return parent[u] = root(parent[u]);
}

int main() {
    int n;
    scanf(" %d", &n);
    for(int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    vector <pair <int, int>> vec;
    for(int i = 1; i <= n; i++) {
        int h;
        scanf(" %d", &h);
        vec.emplace_back(h, i);
    }
    sort(vec.rbegin(), vec.rend());

    int cmp = 0, ans = 0;
    for(auto [h, i] : vec) {
        cmp++;
        appeared[i] = true;
        if(appeared[i - 1] == true) {
            cmp--;
            parent[root(i)] = root(i - 1);
        }
        if(appeared[i + 1] == true) {
            cmp--;
            parent[root(i)] = root(i + 1);
        }

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

Compilation message

gw.cpp: In function 'int main()':
gw.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf(" %d", &n);
      |     ~~~~~^~~~~~~~~~~
gw.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %d", &h);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2600 KB Output is correct
2 Correct 18 ms 2500 KB Output is correct
3 Correct 24 ms 2572 KB Output is correct
4 Correct 25 ms 2500 KB Output is correct
5 Correct 23 ms 2600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 22524 KB Output is correct
2 Correct 254 ms 22432 KB Output is correct
3 Correct 264 ms 22436 KB Output is correct
4 Correct 263 ms 22416 KB Output is correct
5 Correct 252 ms 21812 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 21788 KB Output is correct
2 Correct 250 ms 21756 KB Output is correct
3 Correct 261 ms 21824 KB Output is correct
4 Incorrect 217 ms 15900 KB Output isn't correct
5 Halted 0 ms 0 KB -