Submission #516319

#	Time	Username	Problem	Language	Result	Execution time	Memory
516319		Jomnoi	Global Warming (NOI13_gw)	C++17	40 / 40	250 ms	15864 KiB

gw

#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 (stderr)

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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11