Submission #674405

#	Time	Username	Problem	Language	Result	Execution time	Memory
674405		vjudge1	Global Warming (NOI13_gw)	C++17	40 / 40	211 ms	22332 KiB

gw

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11