Submission #889036

#	Time	Username	Problem	Language	Result	Execution time	Memory
889036		dwuy	Global Warming (NOI13_gw)	C++14	40 / 40	213 ms	25544 KiB

gw

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