Submission #1344661

#TimeUsernameProblemLanguageResultExecution timeMemory
1344661yumemystery지구 온난화 (NOI13_gw)C++20
0 / 40
138 ms20008 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>root;

int findroot (int a) {
	if (root[a] == -1 || root[a] == a) return a;
	return root[a] = findroot(root[a]);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	vector<pair<ll,int>>A(n);

	root.resize(n,-1);

	for (int i=0; i<n; i++) {
		cin >> A[i].first;
		A[i].second = i;
	}

	sort(A.begin(),A.end());
	reverse(A.begin(),A.end());

	int ans = 0;

	for (auto &h : A) {
		int i = h.second;
		
		if (i+1 < n) {
			if (i-1 >= 0) {
				if (root[findroot(i-1)] == -1 && root[findroot(i+1)] == -1) {
					root[i] = i;
					++ans;
				}
				else {
					if (root[findroot(i-1)] != -1) root[i] = findroot(i-1);
					else root[i] = findroot(i+1);
				}
			}
			else {
				if (root[findroot(i+1)] == -1) {
					root[i] = i;
					++ans;
				}
				else root[i] = findroot(i+1);
			}
		}
		else if (i-1 >= 0) {
			if (root[findroot(i-1)] == -1) {
				root[i] = i;
				++ans;
			}
			else {
				root[i] = findroot(i-1);
			}
		}
	}

	cout << ans;
}
#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...