oj.uz

Submission #366336

# Submission time Handle Problem Language Result Execution time Memory
366336 2021-02-14T03:13:21 Z kshitij_sodani Po (COCI21_po) C++14
70 / 70
 52 ms 13676 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo n;
llo it[100001];
llo par[100001];
llo vis[100001];
llo find(llo no){
	if(par[no]==no){
		return no;
	}

	par[no]=find(par[no]);
	return par[no];
}
llo cur=0;
void merge(llo aa,llo bb){
	if(vis[aa]==0 or vis[bb]==0){
		return;
	}
	llo x=find(aa);
	llo y=find(bb);
	if(x!=y){
		par[x]=y;
		cur--;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		par[i]=i;
	}

	map<llo,vector<llo>> ss;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		if(it[i]!=0){
			ss[-it[i]].pb(i);
		}
	}
	llo ans=0;
	for(auto j:ss){
		set<llo> kk;
		for(auto i:j.b){
			cur++;
			vis[i]=1;
			if(i>0){
				merge(i,i-1);
			}
			if(i<n-1){
				merge(i,i+1);
			}
		}
		for(auto i:j.b){
			kk.insert(find(i));
		}
		ans+=kk.size();
	}

	cout<<ans<<endl;






 
	return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 12 ms 2156 KB Output is correct
5 Correct 19 ms 3052 KB Output is correct
6 Correct 39 ms 8172 KB Output is correct
7 Correct 52 ms 13676 KB Output is correct