제출 #1333387

#제출 시각아이디문제언어결과실행 시간메모리
1333387michael12지구 온난화 (NOI13_gw)C++20
0 / 40
235 ms39712 KiB
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<array>
#include<algorithm>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
const int oo = 1e18;
struct DSU{
    int n;
    vector<int> p;
    vector<int> sz;
    DSU(int size){
        n = size;
        p.resize(n + 1);
        sz.resize(n);
        for(int i = 0; i < n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
    int find(int u){
        if(u == p[u]) return u;
        return p[u] = find(p[u]);
    }
    void unite(int u, int v){
        int a = find(u);
        int b = find(v);
        if(a != b){
            if(sz[a] < sz[b]) swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
        }
    }

};
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    vector<pair<int, int>> B(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        B[i].ff = a[i];
        B[i].ss = i;
    }
    DSU dsu(n);
    sort(B.rbegin(), B.rend());
    int mx = -1;
    int ans = 0;
    vector<bool> used(n, false);
    for(int i = 0; i < n; i++){
        ans += 1;  
        used[B[i].ss] = true;
        int T = B[i].ss;
        if(i > 0 && B[i].ff != B[i - 1].ff){
            if(T > 0 && used[T - 1]){
                dsu.unite(T, T - 1);
                ans -= 1;
            }
            if(T < n - 1 && used[T + 1]){
                dsu.unite(T, T + 1);
                ans -= 1;
            }
            mx = max(mx, ans);
        }

    }
    cout << mx;


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...