oj.uz

Submission #516319

# Submission time Handle Problem Language Result Execution time Memory
516319 2022-01-21T05:24:04 Z Jomnoi Global Warming (NOI13_gw) C++17
40 / 40
 250 ms 15864 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 = 1;
    for(int v = 0; v < n; v++) {
        auto [h, i] = vec[v];
        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);
        }

        if(v + 1 < n and vec[v].first != vec[v + 1].first) {
            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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1860 KB Output is correct
2 Correct 20 ms 2104 KB Output is correct
3 Correct 21 ms 2116 KB Output is correct
4 Correct 22 ms 2116 KB Output is correct
5 Correct 20 ms 2116 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1860 KB Output is correct
2 Correct 16 ms 1860 KB Output is correct
3 Correct 23 ms 1816 KB Output is correct
4 Correct 23 ms 1860 KB Output is correct
5 Correct 21 ms 1760 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 13084 KB Output is correct
2 Correct 240 ms 13056 KB Output is correct
3 Correct 240 ms 13084 KB Output is correct
4 Correct 239 ms 13068 KB Output is correct
5 Correct 231 ms 13084 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 13180 KB Output is correct
2 Correct 241 ms 13084 KB Output is correct
3 Correct 239 ms 13088 KB Output is correct
4 Correct 228 ms 13100 KB Output is correct
5 Correct 216 ms 15864 KB Output is correct