Submission #762463

#	Time	Username	Problem	Language	Result	Execution time	Memory
762463		stefanneagu	Global Warming (NOI13_gw)	C++17	23 / 40	435 ms	26204 KiB

gw

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