Submission #674405

#TimeUsernameProblemLanguageResultExecution timeMemory
674405vjudge1Global Warming (NOI13_gw)C++17
40 / 40
211 ms22332 KiB
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int par[N], n;
bool mark[N];
ii a[N];

int anc(int u)
{
    return par[u] == u ? u : par[u] = anc(par[u]);
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) 
        cin >> a[i].F, a[i].S = i, par[i] = i;
    sort(a + 1, a + 1 + n, greater<ii>());
    
    int cnt = 0, res = 0;
    for(int i = 1; i <= n; i++)
    {
        cnt++;
        int pos = a[i].S;
        mark[pos] = 1;
        if(mark[pos - 1])
        {
            cnt--;
            par[pos] = anc(pos - 1);
        }
        if(mark[pos + 1])
        {
            cnt--;
            par[pos] = anc(pos + 1);
        }
        if(i < n && a[i].F != a[i + 1].F)
            res = max(res, cnt);
    }
    cout << res;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}
#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...