oj.uz

Submission #762478

# Submission time Handle Problem Language Result Execution time Memory
762478 2023-06-21T12:28:37 Z stefanneagu Global Warming (NOI13_gw) C++17
40 / 40
 399 ms 25612 KB 
#include <iostream> 
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int nmax = 1e6 + 7;

struct insula {
    int val, ind;
} v[nmax];

int root[nmax], sum[nmax];
bool f[nmax];

bool cmp(insula a, insula b) {
    return a.val > b.val;
}

int find(int x) {
    if(root[x] == x) {
        return x;
    }
    root[x] = find(root[x]);
    return root[x];
}

void unite(int a, int b) {
    if(sum[a] < sum[b]) {
        swap(a, b); 
    }
    sum[a] += sum[b];
    root[b] = a;
}

int32_t main() {
    int n, maxx = 0, cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> v[i].val;
        v[i].ind = i;
    }
    sort(v + 1, v + n + 1, cmp);
    for(int i = 1; i <= n; i ++) {
        f[v[i].ind] = 1;
        if(f[v[i].ind - 1] == 0 && f[v[i].ind + 1] == 0) {
            cnt ++;
            root[v[i].ind] = v[i].ind;
            sum[v[i].ind] = 1;
        } else if(f[v[i].ind - 1] == 1 && f[v[i].ind + 1] == 0) {
            root[v[i].ind] = v[i].ind;
            sum[v[i].ind] = 1;
            unite(v[i].ind, find(v[i].ind - 1));
        } else if(f[v[i].ind + 1] == 1 && f[v[i].ind - 1] == 0) {
            root[v[i].ind] = v[i].ind;
            sum[v[i].ind] = 1;
            unite(v[i].ind, find(v[i].ind + 1));
        } else {
            cnt --;
            root[v[i].ind] = v[i].ind;
            sum[v[i].ind] = 1;
            unite(v[i].ind, find(v[i].ind + 1));
            unite(find(v[i].ind), find(v[i].ind - 1));
        }
        if(v[i].val != v[i + 1].val) {
            maxx = max(maxx, cnt);
        }
    }
    cout << maxx;
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2132 KB Output is correct
2 Correct 19 ms 2140 KB Output is correct
3 Correct 19 ms 2116 KB Output is correct
4 Correct 19 ms 2096 KB Output is correct
5 Correct 19 ms 2132 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2808 KB Output is correct
2 Correct 27 ms 2600 KB Output is correct
3 Correct 36 ms 2692 KB Output is correct
4 Correct 36 ms 2724 KB Output is correct
5 Correct 34 ms 2740 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 19488 KB Output is correct
2 Correct 385 ms 18180 KB Output is correct
3 Correct 399 ms 18212 KB Output is correct
4 Correct 384 ms 18208 KB Output is correct
5 Correct 374 ms 18296 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 19456 KB Output is correct
2 Correct 386 ms 25612 KB Output is correct
3 Correct 380 ms 25512 KB Output is correct
4 Correct 204 ms 19672 KB Output is correct
5 Correct 216 ms 19636 KB Output is correct