oj.uz

Submission #889036

# Submission time Handle Problem Language Result Execution time Memory
889036 2023-12-18T16:21:55 Z dwuy Global Warming (NOI13_gw) C++14
40 / 40
 213 ms 25544 KB 
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

struct DSU{
    int n;
    vector<int> e;
    vector<bool> active;

    DSU(int n=0){
        this->n = n;
        this->e.assign(n+5, -1);
        this->active.assign(n+5, 0);
    }

    int fp(int u){
        return e[u] < 0? u : e[u] = fp(e[u]);
    }

    bool unon(int u, int v){
        if(!active[u] || !active[v]) return 0;
        u = fp(u);
        v = fp(v);
        if(u == v) return 0;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return 1;
    }
};

const int MX = 1000005;

int n;
pii a[MX];

int gw(int N, int H[]){
    n = N;
    for(int i=1; i<=n; i++) a[i] = {H[i-1], i};
    sort(a+1, a+1+n, greater<pii>());

    DSU dsu(n);
    a[0].fi = -1;
    int ans = 0;
    int cur = 0;
    for(int i=1; i<=n; i++){
        if(a[i].fi != a[i-1].fi) ans = max(ans, cur);
        cur++;
        dsu.active[a[i].se] = 1;
        cur -= dsu.unon(a[i].se, a[i].se-1);
        cur -= dsu.unon(a[i].se, a[i].se+1);
    }
    return ans;
}

int32_t main(){
    fastIO;
    //file(TASK);

    int n;
    cin >> n;
    int h[n];
    for(int i=0; i<n; i++) cin >> h[i];

    cout << gw(n, h);

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3584 KB Output is correct
2 Correct 15 ms 3676 KB Output is correct
3 Correct 15 ms 3676 KB Output is correct
4 Correct 15 ms 3648 KB Output is correct
5 Correct 15 ms 3676 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4188 KB Output is correct
2 Correct 10 ms 3932 KB Output is correct
3 Correct 17 ms 4172 KB Output is correct
4 Correct 18 ms 4188 KB Output is correct
5 Correct 16 ms 4032 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 25368 KB Output is correct
2 Correct 181 ms 25544 KB Output is correct
3 Correct 179 ms 25368 KB Output is correct
4 Correct 213 ms 25332 KB Output is correct
5 Correct 172 ms 24700 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 24820 KB Output is correct
2 Correct 184 ms 24656 KB Output is correct
3 Correct 191 ms 24700 KB Output is correct
4 Correct 175 ms 18860 KB Output is correct
5 Correct 160 ms 19064 KB Output is correct