Submission #1174102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174102		nuutsnoynton	Global Warming (NOI13_gw)	C++20	40 / 40	183 ms	32760 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};

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];
	vector < pair < ll, ll > > v;
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
		v.push_back(make_pair(a[i], i));
	}
	sort(v.rbegin(), v.rend());
	
	ans = 0;
	for (i = 0; i < v.size(); i ++) {
		s = v[i].first;
		while ( i < v.size() && v[i].first == s) {
			ll X = v[i].second;
			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);
			i ++;
		}
		i --;
		ans = max(ans, cnt);
	}
	cout << ans << endl;

}

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