oj.uz

Submission #762463

# Submission time Handle Problem Language Result Execution time Memory
762463 2023-06-21T12:22:48 Z stefanneagu Global Warming (NOI13_gw) C++17
23 / 40
 435 ms 26204 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));
        }
        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 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 19 ms 2236 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 36 ms 2804 KB Output is correct
2 Correct 26 ms 2620 KB Output is correct
3 Correct 36 ms 2740 KB Output is correct
4 Correct 36 ms 2744 KB Output is correct
5 Correct 35 ms 2752 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 25028 KB Output is correct
2 Correct 394 ms 26204 KB Output is correct
3 Correct 385 ms 26160 KB Output is correct
4 Correct 395 ms 26172 KB Output is correct
5 Correct 372 ms 25548 KB Output is correct

Subtask #5
0 / 11.0

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