Submission #1174098

#TimeUsernameProblemLanguageResultExecution timeMemory
1174098nuutsnoyntonGlobal Warming (NOI13_gw)C++20
12 / 40
1099 ms117008 KiB
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e6 + 2;
ll ataman[N], cnt;
bool used[N] = {0};
vector < ll > v[N];

ll Get(ll x) {
	if ( x == ataman[x]) return x;
	return ataman[x] = Get(ataman[x]);
}

void Unite(ll x, ll y) {
	x = Get(x);
	y = Get(y);
	if ( x == y) return ;
	cnt --;
	if ( x > y) swap(x, y);
	ataman[y] = x;
	return ;
}


int main() {
	ll n, m, r, x, s, y, i, j, ans, t;

	cin >> n;
	
	ll a[n + 2];
	map < ll, ll > mp_1, mp_2;
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
		mp_1[a[i]] ++;
	}
	s = 0;
	
	for ( auto R : mp_1) {
		mp_2[R.first] = ++s;
	}
	
	for (i = 1; i <= n; i ++) {
		a[i] = mp_2[a[i]];
		v[a[i]].push_back(i);
	}
	
	ans = 0;
	for (i = 1e6; i >= 0; i --) {
		for ( ll X : v[i]) {
			used[X] = 1;
			cnt ++;
			ataman[X] = X;
			if ( used[X - 1] == 1) Unite(X, X - 1);
			if ( used[X + 1] == 1) Unite(X, X + 1);
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;

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