oj.uz

Submission #762461

# Submission time Handle Problem Language Result Execution time Memory
762461 2023-06-21T12:21:19 Z stefanneagu Global Warming (NOI13_gw) C++17
13 / 40
 57 ms 5532 KB 
#include <iostream> 
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int nmax = 2 * 1e5 + 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));
        }
        maxx = max(maxx, cnt);
    }
    cout << maxx;
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 340 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2212 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 37 ms 2748 KB Output is correct
2 Correct 26 ms 2476 KB Output is correct
3 Correct 35 ms 2784 KB Output is correct
4 Correct 43 ms 2728 KB Output is correct
5 Correct 42 ms 2676 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 5532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 5444 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -