Submission #1174099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174099		nuutsnoynton	Global Warming (NOI13_gw)	C++20	0 / 40	557 ms	131072 KiB

gw

#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() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n, m, r, x, s, y, i, j, ans, t;

	cin >> n;
	
	ll a[n + 2];
	unordered_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;

}

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