Submission #366336

#	Time	Username	Problem	Language	Result	Execution time	Memory
366336		kshitij_sodani	Po (COCI21_po)	C++14	70 / 70	52 ms	13676 KiB

Main

//#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 / 70